Linear Convergence of Gradient Methods for Estimating Structured Transition Matrices in High-dimensional Vector Autoregressive Models
Authors: Xiao Lv
Wei Cui
Yulong Liu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Vector autoregressive models
dirty statistical models
linear convergence rate
non-asymptotic analysis

Abstract: In this paper, we present non-asymptotic optimization guarantees of gradient descent methods for estimating structured transition matrices in high-dimensional vector autoregressive (VAR) models. We adopt the projected gradient descent (PGD) for single-structured transition matrices and the alternating projected gradient descent (AltPGD) for superposition-structured ones. Our analysis demonstrates that both gradient algorithms converge linearly to the statistical error even though the strong convexity of the objective function is absent under the high-dimensional settings. Moreover our result is sharp (up to a constant factor) in the sense of matching the phase transition theory of the corresponding  model with independent samples. To the best of our knowledge, this analysis constitutes first non-asymptotic optimization guarantees of the linear rate for regularized estimation in  high-dimensional VAR models. Numerical results are provided to support our theoretical analysis.

Linear Convergence of Gradient Methods for Estimating Structured Transition Matrices in High-dimensional Vector Autoregressive Models
Xiao Lv, Wei Cui School of Information and Electronics Beijing Institute of Technology (xiaolv, cuixei]@bit. edu. cn
Yulong Liu" School of Physics Beijing Institute of Technology iallonllu@bii edu. cn
Abstract
In this paper, we present non-asymptotic optimization guarantees of gradient de- scent methods for estimating structured transition matrices in high-dimensional vector autoregressive (VAR) models. We adopt the projected gradient descent (PGD) for single-structured transition matrices and the alternating projected gradi- ent descent (AltPGD) for superposition--ttuuuuued ones. Our analysis demonstrates that both gradient algorithms converge linearly to the statistical error even though the strong convexity of the objective function is absent under the high-dimensional settings. Moreover our result is sharp (up to constant factor) in the sense of matching the phase transition theory of the corresponding model with indepen- dent samples. To the best of our knowledge, this analysis constitutes first non- asymptotic optimization guarantees of the linear rate for regularized estimation in high-dimensions VAR models. Numerical results are provided to support our theoretical analysis.
Introduction
Learning the network structure through high-dimensional time series data has been an important focus of research for the past decades. There are lots of application examples ranging from macroeconomic analysis [+3 to connectivity measuring among financial firms [4], gene regularity network inference [5] and radar signals processing 16. 77 To perform these tasks, vector autoregressive (VAR) models play a critical role both theory and application. For example, VAR models are widely adopted to characterize the spatially and temporally colored disturbance for multichannel adaptive signal detection in [Z-II.
Under the low-din diwddimensioal settings where the dimension of the transition matrix and the number of time series are relatively small, the theory VAR models is well established, see e.g., [12] However, lots of meaningful applications are under the nigh-dimensional settings where the problem dimension far exceeds the number of time series and additional structure information of parameters required guarantee successful recovery. For the cases where the samples are independent, both theoretical properties and practical algorithms of high-dimensional statistical problems have been studied by considerable literature during the past few years, including but not limited to (3317]. For the correlated time series cases, the corresponding results are still developing. By assuming that the spectral norm of the transition matrix is less than 1, Loh and Wainwright consider VAR models regularized by the 1 norm in [18]. Under the double asymptotic framework, Han and Liu also consider VAR models under the similar assumption in 19). In (0),, Basu and Michailidis analyze sparse transition matrices estimation of VAR models with a milder stability assumption by
"Corresponiing author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

introducing the spectral density. Recently, Melnyk and Banerjee extend the analysis to structured VAR models regularized by any suitable norm in (2T]
Compared with the progress on the statistical analysis of VAR models, much less is known about their computational issues. For instance, Basu et al. [22] make exploration in this direction by proposing the fast network structure learning algorithm (FNSL) for the penalized recovery procedure. Their
analysis does take the structure information of the parameter into account and only establishes a sub-linear convergence rate for the FNSL.
In this paper, first provide the non-asymptotic optimization guarantee of PGD for VAR models with single- angle-structured transition matrices. Our analysis illustrates that the distance between iteration points of PGD and the real transition matrix would converge linearly to the statistical error despite the objective function is not strongly convex under the high-dimensional settings. Our result sharp in the sense that the minimal requirement of samples to guarantee the linear rate matches the phase transition of the model with independent samples up to a constant factor.
On the other hand, considering the parameter to be estimated only has one type of low-dimensional structure or single-structured might be too oversimplified for messy real applications. So superpositioon-sttuuuurre models have received more attention of researchers in last decade. Typical examples include robust PCA 23 24),, multi-task learning [25] and robust matrix sensing [26]. For these scenarios, employ AltPGD to solve related optimization problems and establish the corresponding non asymmmotmtiic optimization guarantee. Our results show that AltPGD also enjoys a linear convergence rate, which is much more efficient than the sub-linear rate in 22 At the same time, our analysis avoids a drawback in [22 that the estimation error does not converge to zero when the number of measurements approaches infinity.
Last but not the least, we also illustrate that AltPGD is a practical algorithm to solve the general superpositionn-strctuue statistical model in (27). Apart from the time series case, our analysis also adapts to multi-task learning and robust PCA.
2 Problem formulation
In this paper, we consider a d-dimensional vector-valued stationary time series ("o.....a) gen- erated by VAR model of lag with serially uncorrelated Gaussian errors. The VAR(I) model is defined as
Ft++1 r x. + ec+t,
0, .,... ,,
where r, E IRdxd is the transition matrix and e, the matrix form
sid ~ (O, Ex). This model can be reformulated in
Y = XT. E,
(2)
where Y = [x1, IT E Raxd X [ xn-1) E gaxd and E [e e,, E Raxd
The goal of the VAR(I) model is to recover the transition matrix r, from the observation matrix Y and the data matrix X. the high-dimensional settings with n < d², tractable recovery is possible when the transition matrix r, is well structured. Thus we introduce convex regularizer R(.) to promote the structure of r,, Then a popular way to estimate r, to solve the following constrained least square problem
1 Y XT
min
-
2n
(3)
s.t. R(T) R(T.).
where || ||p represents the Frobenius norm of a matrix.
When the transition matrix T, is cnnerpositioo-sstuutueee in which r, is the sum of two single- structured components, i.e., r, = S, + L,, we adopt two convex functions Rs(-)) and (.) to
characterize the structures of its two components and solve the following constrained problem to

---

estimate S, and L.
min 1 Y X(S + D)ll: S.L
s.t. Rg(S) - (s().), RL(L) S (L...).
3 Single-structured transition matrices estimation via PGD
In this part, we consider the where the transition matrix be estimated in only has one type of low-dimensional structure which is characterized by convex function R(-). To estimate the transition matrix T., we solve the problem (3) via the PGD update (summarized in Algorithm I
By setting fn (T) Y XT (2n)). we could write the iteration of PGD
D = Px (T))).
(5)
where is the step size, KC = {T R(T) S. RTT)) is the descent set and Px represents the orthogonal projection onto the K. We also introduce the concept of the descent cone cone(K - r.), where cone(-) is the conic hull of set.
Algorithm 1 PGD for single-structured transition matrices estimation Input: Initial point To step size μ4, iteration number K. for k to K 1 do
F Fx+1 = (Tx (Tx))
end for Output: T
To guarantee consistent estimation, we propose the following stability assumption for the VAR model which also imposed in (0 [22]
Assumption (Stability). The characteristic polynomial the
the VAR model (I) satisfies dct(A(z)) +
on the unit circle of the complex plane {z E C: |a| = =], where A(z) = Taxd r
In the non-asymptotic analysis of the VAR model we use the following two quantities
M(fa) ess sup Amax (0)),
(6)
0 n
m(fa) ess inf Amin (0)) 0E न.
(7)
where (0) is the spectral density function defined as
Σ (0) = 2TT
1
Ex(eee 100
0 [].
(8)
1=-00
Here we use (,)) to represent
=
1,1 Z.
(9)
Specially, we write (0 = Σg for simplicity.
Compared with the model with independent samples, there is dependency among the rows of data matrix in the VAR model (2). which is the main challenge when deriving the deviation bounds required by the estimation problem. For Gaussian processes, this dependency could be characterized by the covariance matrix Y,
veex"""x"""""] where vec(-) represents the column- wise vectorization of matrix. The following lemma indicates that the concept of the spectral density function is a convenient tool to bound the extreme eigenvalues of Y...
Lemma 1 (Proposition 2.3 in (20). Donate Y. E[vec(X"*) )vec(( T where X is the data matrix in the VAR model (2). We could bound the extreme eigenvalues of as
2mm(f²) S Amain (X.) S (f,x < (mx(
(10)
In particular, we also have
2xm(fa) S Amin (Ex) S Amax (Ex) < 2T
(11)
3

---

For stable and invertible ARMA processes which include the model T the spectral density & has closed form expression based on the matrix valued polynomials [2]] Equation (2.4)). Furthermore. the concrete calculation of the upper bound of MMfz) and the lower bound of m({f2) for the model ①1 is provided from zero and infinity. In this way, we could introduce the quantities Kiii and Kmax to simplify the expression of our analysis.
(2 Proposition 2.2] which indicates m(f=) and M(Jz) could be bounded away
Assumption (Boundness). Suppose there are positive constants Kminn and Kimax satisfying
0 <
Kmin
I m(fa) S M(f.) S
Kmax
(12)
2π
2x
With the above assumption, we could represent the extreme eigenvalues of Y, and Σg in a concise way
Emin
S Amin (x,) < Xmax (Tg) S
Kmax
(13)
Amin
Amin
Σx Amax Σx)
Fimax.
(14)
In our analysis, we use the Gaussian width to quantify the size of a set T
(T)
Esup 2), T
where g ~ NN I).
We are now ready to present the non-asymptotic optimization guarantee of PGD for the problem 3
Theorem 1. Consider the VAR model satisfying Assumptions 7 and 2 Suppose r, is single-
structured and R(-)) is a convex function. Starting from a point To satisfying R(To) S RT,)), we solve the optimization problem measurements satisfies
33) via PGD with the step size μ 1/Nimxx- If the number of
/n > 20 Kunax (w(C n Sp) u).
(15)
Einin
then the PGD update would obey
[ - F.lF S k+1 To - -r.le E
sptt1
(16)
p
with probability at least 1 cexp(-up? Here
Emin
wCC (CC()sp)= +
Rmin
p 1
+
1
(17)
Kmax
Vn
2kmax
wWCnspp +
{ = C
Ee
(18)
v
Fmuax
Vn
wCC + u
< 20 Vimax ||
wWCns +
C²
Ee
(19)
VKmax
Vn
Kmin
Vn
|| || represents the spectral norm of a matrix, Sp represents the sphere with unit Frobenius norm and e, C, C' are absolute constants.
Remark (Sharpness). Our result demonstrates that PGD can converge linearly to the statistical ervor despite the objective function fT' is not strongly convex under the high-dimensional settings. And the linear convergence is achieved when the number of measurements of order w(C )²)
which matches the phase transition of the model with independent samples [15 T6].
Remark (Impact of correlated samples). Our result also provide some insights for the impact of correlated samples. It is not hard to find that the temporal dependency is characterized by Kmax and Emii which appear in the convergence rate, the estimation error, and the required number of samples. Let K Kmax/ Kmiin Clearly, smaller h. will lead to faster convergence rate with smaller required samples and estimation error.
Remark (Comparison with related works). The existing works on structured VAR models such as 119 are muinly concerned with estublishing the statistical error bounds for different recovery procedures. Our work focuses on algorithmic analysis and reveals how many samples would ensure that the algorithm achieves a fast convergence rate. On the other hand, our work could be regarded

---

as a generalization of the result in [17] from independent samples to time series. This generalization nontrivial, since new mathematical tools (e.g.. two deviation inequalities: Lemmas 4 and are required to address time-series settings. To the best of our knowledge, Lemma 5 seems to be the first non-asymptotic result for the VAR models which yields the unifted estimation error bounds for both independent and correlated samples. Furthermore, our analysis demonstrates PGD enjoys a linear convergence for structured VAR models, which is much more efficient than the sub-linear convergence rate of FNSL in [22]. Additionally, the linear convergence rate of PGD is also illustrated in (18) for the VAR(I) I) model with a sparse transition matrix, when the spectral norm of the transition matrix is strictly less than 1. Compared with the result in [18,, our analysis adapts to general structured signals with the milder Assumption !
set the step size μ f/max for concise expression of the result. fact, any step size satisfying μ S K/ma could achieve a linear convergence rale by providing the corresponding number of measarements. In 120 21). VAR(d) models are reformulated as VAR(T) models. With the same reformulation, our analysis also adapts to VAR(d) models.
Remark 4 (Extension). In Theorem
Our analysis for the VAR model (I) also adapts the multi-task learning problem with inde- pendent samples| |
Different from the time series setting, the measurements Y XT, + E in
this case are generated from It iid (O, Ez) and et
sid NO E.), for 1, .. n, where E Raxd are independent.
X 2",,".. ,T,,,²' E Raxd and E E= (ei..... ,enl²
Corollary 1. Consider the multi-tas task learning problem with the above conditions. Under Assumption 2 we solve the optimization problem (3) via PGD with the step size μ 1/Kmax and starting point
To satisfying oT) I R.),)) If the number of measurements satisfies
Vn > 20 Krnax (u(CSSp) u),
(20)
Kmin
then the update 5 would obey
[[ - IF < (1 Kiiin g++ [To - IF + 20" y Fimax
(C
E
(21)
2kmax
Kmin
vn
with probability at least 1 (exp((=u), where c. C, C' are absolute constants.
4 Superpasition-strucuured transition matrices estimation with AltPGD
In this part, we consider the case where the transition matrix T, to estimated in ( is superposition- structured, that is, r. S. L.. To estimate S, and L,, solve the optimization problem via AltPGD (summarized in Algorithm?? 2.
We set LS) = |Y xSS + L)Il (2n) and write the update of AllPGD as
S Px. (Sy. s. L&)), L Px, (Ls - VV (Sx, Lx)),
(22)
where K.s = {S) RS( < Rs((S)) and Kr. [L Rr.(L) < Rr We also introduce two descent cones Cs = cone(K.s S.) and Cr. = cone(K,, L.), which would be used in our analysis.
Algorithm 2 AlPPGD for superpositioon transition matrices estimation
Input: Initial points So and Lo. step size μ. iteration number K. for K 1 do
S = Px2 Se 4V Sf Lx)) L Pk, [L Ln Lt))
end for Output: Sx and LK
In this part, we consider R-(()) and (.).)) both belong to decomposable norms defined in 14
In addition, our analysis framework could also be used in the problem to estimate r. and the precision matrix Σ, simultaneously 28
5

---

Definition 1 (Decomposable norm). A regularization function R(-) is decomposable with respect to a subspace pair (M,M+) if R(a + 3) R(a) + R(3), M, 3 M-
(23)
Here, .M is referred to as the model subspace which captures the constraints determined by the model and M S M. M is called the perturbation subspace indicating the deviation from the model subspace M.
For common structure priors such as sparsity, group-sparsity and low-rank property, the corresponding regularization functions nonrr,, norm and nuclear norm all belong to decomposable norms with low-dimensional model subspaces.
For the superposition -truucuurd transition matrix r, S. + L... we assume (-(() decomposable with respect subspace pair (Ms, which is suit for the single-structured parameter S.. Similarly, (-) is decomposable with respect a subspace pair (Mc, M²) suit for L..
Due to the superposition -ttrrccurdd property of the transition matrix, we need to impose an additional assumption about the interaction between the two different structured components to guarantee the separate estimation.
Assumption (Structural incoherence). Given the subspace pairs (Ms, Mss and (Mc. M22 for the two parameters S, and L.. Suppose the covariance matrix Eg defined in (9) satisfies
max max (PMs ExP J...M ( MePM
Fmnax (P Mg E.P xzt δ max (P PMg
E.P (ePmmt)) S
Kmiin
(24)
8
where m (.) for matrix E is desined as F E)=
sup v.UeSr
(V, ΣU> and Kmin is defined
in 12 Here PM MM P PMg and PMt donate the orthogonal projection operators onto the corresponding subspaces.
Remark (Related works). Several similar assumptions have been imposed in [27
29 30/. This
rype of assumptions is first proposed by Yang and Ravikumar in [271, where they use the structural incoherence assumption to restrict the interaction between different components of superposition- structured statistical models and the C-Linear condition guarantees the structural incoherence under the linear regression setting and the Gaussian design. Meng et al. generalize the C-Linear assumption to the Structural Fisher Incoherence assumption in (29) for the estimation of sparse plus low-rank matrices in Gaussian Graphical Models. In (30], Greenewald and Hero introduce the structural incoherence assumption to robust Kronecker product PCA models. Our Assumption 3 is also motivated by (27) and would reduce to the C-Linear condition in (27) when we consider Gaussian ensemble where the rows of X in (2) are generated independently from (0, Ex).
Remark 6 (Nonidentifiability... There are also other conditions used in literature to deal with the nonidentifiability concern. In (22)) Basu et al. refer to the spikiness condition, which is first introduced in 131] for matrix completion and then is extended to matrix decomposition in (32). In 127), Yang and Ravikumar compare the structure incoherence used here with the spikiness condition and illustrate the structure incoherence could address drawback of the spikiness condition that the estimation error does not approach zero when the number of samples approaches infinity and requires weaker conditions at the same time. Another common condition used in [23) [6] for sparse plus low-rank matrices recovery is the incoherence condition which is first proposed in [33 34). In 33 32), the authors illustrate that the spikiness condition is milder condition than the incoherence condition and is more suitable for the noisy models because of the consideration of singular values.
We now present the non-asymptotic optimization guarantee of AltPGD for the problem
Theorem 2. Consider the VAR model (1 satisfying Assumptions 7 and 3 Suppose r. is superposition-
and r, = S. + L... where S. and L,, are two single- strucl--tructured parameters whose structures are characterized by two decomposable norms R.((-) and Ri(.) respectively. Start- ing from points So and Lo satisfying Rs(Su) & RS(S.) and R (Lo) I (L..... we solve the optimization problem (4) via AltPGD with the step size μ 1/ L/Kmaxx If the number of measurements satisfies
Vn 40 40 Manax (SF) wC2 (8p) + u),
(25)
Kyai

---

then the update (22 would obey
5
| -.llF ||
L. S (1So -S.IF + -o L.1l)) +
(26)
1 1-p p
with probability at least cexp(- Here
3 Mmuin
+ C (Sp) + w(Cs nSp) +
Kmin
(27)
Kmax
vni
2kmax
WCC nSp) + w(Cs (Sp) + w
1- P C²
Vimax S
P
vn
< 20 VKimax
E W(CL + w(S 7Sp) +u
(28)
Fimin
vn
and c, C, C are absolute constants.
Remark 7 (Related works). Our analysis makes progress on three aspects compared with the result in (22). First, we illustrate the linear convergence rate of AlPGG compared with the sub-linear rate of FNSL. Second, our analysis indicates the requirement of samples for the linear rate and the statistical error, which are absent in the analysis of optimization in [22]. Third, Theorem 2 drawback of the result in (22) that the estimation error does not converge zero when the number of samples approaches infinity.
Our analysis framework is also valid for robust PCA considered in [32 27 Suppose we have i.idd. sample 2; E Rd, where 2, = u, + U₁ Ue ~ (0, L.), D; ~ (0, S.), u, and U, are independent. Here L, is low-rank matrix and S, is a sparse matrix. We could write the sample matrix as Y = >y x = L. + S. + E, where E matrix. In this setting, we have the data matrix X
>i= スं - (L. + S.) is a Wishart noise lax and solve the problem
min S.L
Y --S- -Il
(29)
s.t. ||vec( ST )11 S lIveo(( (S. |L|, S |..
where || represents the 1 nnom of a vector and || 11, represents the nuclear norm of a matrix.
Corollary 2. Consider the robust PCA model where S, a sparse matrix with s, non-zero entries and L, is r.-rank matrix. Under Assumption 3 where Σ,- = Laxd and Kmin Kmax 1 in this setting. we solve the optimization problem (29) via AltPGD with the step size μ and starting
points So and Lo satisfying [|vec(()) I [ive((S)] and [oll I [. If the number of measurements satisfies
Vn > C'(Vs, s. log d + Vr,d+u),
(30)
then the update of AltPGD would obey
|| SxIlp || L.
1 ( (1S. 3
Salle + Lo L.ll)) + 4 cls. + L. Vs, L. log d
+ vr.d +
(31)
3
Vn
with probability at least 1 cexp(-u2). Here C and C' are absolute constants.
5
Numerical results
5.1 Synthetic data
In this section, we apply PGD and Al|PGD to network learning problems and compare the perfor- mance with FNSL proposed in (22). We regularize sparse matrices by the no-mo and low-rank matrices by the nuclear norm All simulations run PC with Intel i5 15-5500 and 16GB memory.
'The step size is selected as the inverse of the maximum eigenvalue of the estimated covariance matrix of the samples and the estimated covariance matrix is derived from X X /n.
'The projection onto the L -nom ball follows the procedure in (35) and the projection onto the nuclear norm ball is union of the singular value decomposition and the projection onto the 4 no-rrmm ball.
7

---

We first introduce several performance metrics for network estimation. For the estimated transition matrix I and the real transition matrix T, whose entries are denoted by fi and 7ig respectively, we define the true positive rate (TPR) and false alarm rate (FAR) as
#(% of 0 and 7ry + 40}
#1 o 0 and 7/3 = 0}
TPR
FAR
#(t + 0}
#17/) 0}
We also introduce the estimation error (EE), where EE T T hppl///// ||-
5.1.1 Network learning with a sparse transition matrix
First we consider Т, E Rddd is a sparse matrix with s, non-zero entries. We suppose each row of Т, has s./d non-zero entries whose values follow standard normal distribution. Then we rescale Т. to guarantee the stability of the process. In this simulation, we set = 100 and s, 3500. To illustrate the effect of the numbers of samples, perform the simulation under three scenarios n 1000, 1500, 2000 and each scenario repeated for 100 trials. For FNSL, we choose the regularization parameter Às O(vn logd) according to Propositions and 3 in [22] Both algorithms start from To- O.
Table 1: Performance comparison between PGD and FNSL on sparse network learning problems
100
Method
TPR (%)
FAR (%)
EE
Total time
PGD
79.49
11.04
0.476
3.18
1000
FNSL
73.64
14.19
0.489
75.59
PGD
83.45
8.91
0.396
5.16
1500
FNSL
78.43
11.62
0.417
140.16
PGD
85.82
7.63
0.350
6.14
n 2000
FNSL
81.30
10.07
0.373
183.79
In Table I we record the experimental results for the two algorithms under different numbers of samples. The results illustrate that PGD enjoys better performance with much less computation time than FNSL and support our analysis in Theorem |
5.1.2 Network learning with a low-rank transition matrix
Then we consider r, E Rdxd is low-rank matrix whose rank r.. Suppose constructed by T. UVT, where U, V E IR are matrices with independent standard Gaussian entries. We also rescale r, to guarantee the stability of the process. We set 100, 8000, r. 2 and repeat the scenario for 100 times. For FNSL, we choose the regularization parameter A as O( ((/d)) according to Propositions and 3 in [22]. The result in Figure ((a) illustrates that the updates of PGD enjoy a faster convergence rate than those of FNSL, as predicted Theorem
PGD
75
Spoere oe www.tateeeeeee ent Sur
100
Melente mne of
llbration
The trandies sumppko 37
The rucald sugge det NiotCan 5y2
(a) Convergence rate
(b) Squared estimation error
(c) Rescaled sample size
Figure Convergence results of PGD for low-rank transition matrices estimation.
We also perform simulations under different dimensions and different numbers samples n to verify the order of estimation emoor where we set r사 and each scenario is repeated for 100 times. The results in Figure [(b) and [[c] indicate that all the squared empirical error curves behave as ft) x 11 and support our theoretical results in Theorem

---

5.1.3 Network learning with superposition-sttuuturrr fransition matrix
In this part, we suppose the transition matrix in the VAR model T is superposition-structee Specially, we consider r, = S. + L., where S. is sparse matrix with 8, non-zero entries and L. is rank-r, matrix. The construction of S. and L. follows the same procedure the above simulations. First, we set 100, s, = 3500 and r. = 2. To illustrate the effect of the numbers of samples, we perform the simulation under three scenarios repeated for 100 trials. For FNSL, we choose the regularization parameters Xş as Ol ((vn log d) and År as nd) according to Propositions and in 22.. Both algorithms start from So 0 and Lu 0.
1500, 2000, 2500 and each scenario is
Table 2: Performance comparison between AltPGD and FNSL estimation of sparse plus low-rank transition matrices
d 100
Method
TPR (%)
FAR (%)
EE
Total time (s)
AltGG
78.26
11.70
0.475
19.16
n 1500
FNSL
71.18
15.52
0.486
309.76
AltPGD
81.06
10.20
0.421
26.05
n = 2000
FNSL.
74.65
13.65
0.438
436.46
AltPGD 83.19
9.05
0.379
32.27
n 2500
FNSL 77.49
12.12
0.399
544.08
In Table 2 we record the experimental results for the two algorithms under different numbers of samples. The results illustrate that AltPGD enjoys better performance with much less computation time than FNSL.
Then we compare the convergence rates of AltPGD and FNSL.. We set d = 100, 8000, s, 3500, r. and repeat the scenario for 100 times. The result in Figure 2(a) illustrates the efficiency of AltPGD.
We also perform simulations under different dimensions d and different numbers of samples to verify the order of estimation error, where we set s. 300, r, = 3 and each scenario is repeated for 100 times. The results in Figure(((b) and [(c) indicate that all the squared empirical error curves behave as ft) x 11 and support our theoretical results in Theorem 2
APPOD
100
d 102
Square wetcuatte one Ave
lleration
The txcubve M7
The coccall doe 200 Sel KG 599
(a) Convergence rate
(b) Squared estimation error
(c) Rescaled sample size
Figure 2: Convergence results of AltPGD for sparse plus low-rank transition matrices estimation.
5.2 Real data
Next, analyze the temporal dynamics of the log-reture of stocks in the S&P 500 index. The stock data consists of 1259 daily closing prices for 434 companies the S&P 500 index between February 8, 2013 and February 7, 2018 [36.. In this way, get 1259 data vectors, each of which contains the closing prices of all stocks on trading day. To ensure the data stationary, we calculate leg-returns [r:)²=] 1--1 of stocks by
Tt llog( PL+1.
t= 1. --1,
(32)
Pt,i

---

where is the closing price of stock i at day t. In this way, we construct the data matrix X PT- and the observation matrix Y =_22.- -1-
We adopt the VAR model T with the regularizer R(-) I study the evolution of stock log-returns over the 2013-2018 period and then solve the model with PGD. The constrained parameter selected through 5-fold cross validation. In Figure we present the sparsity patterns of two parts of the transition matrix N estimated by PGD, which indicate meaningful Granger causal effects (37 38 among the log-returns of stocks. The 434 companies belong to 10 different sectors, such as materials (22 stocks), energy (29 stocks), consumer staples (31 stocks) and financials (83 stocks). Figure 3(a) and 3(b) the log-returns of stocks in the energy sector have stronger Granger causal effects, and the Granger causal effects of the consumer staples sector and the financials sector are weaker. For comparison, we present the sparsity patterns of the transition matrix estimated by FNSL in 22 which illustrate similar Granger causal network.
Consume Stapls
Maternls
62
Energ
Finarda
0.5
2.0
51
115
Matorials
Energy
Consumer Stapes
115
(a) Materials sector and energy sector
(b) Consumer staples sector and financials sector
Figure 3: Sparsity patterns of the transition matrix I' estimated by PGD.
Consumar Stapies
0.8
0.1
Malerials
0.04
52
0.03
Energy
Firancills
0.05
0.5
0.12
51
Materials
23
Energy
Consumer Staples
32
Financials
115
(a) Materials sector and energy sector
(b) Consumer staples and financials sector
Figure 4: Sparsity patterns of the transition matrix f estimated by FNSL.
Acknowledgments and Disclosure of Funding
The authors would like thank the anonymous reviewers for their constructive feedback and suggestions. This work was supported by the National Natural Science Foundation of China under Grants 61971044 and 62025103.
References
[1] J. Fan, J. Lv, and L. Qi. "Sparse high-dimensiona. models in economics," Annual Review of Economics, vol. 3, pp. 291-3177 Sept. 2011.
10

---

[2] C. De Mol, D. Giannone, and L. Reichlin, "Forecasting using large number of predictors: Is Bayesian shrinkage valid alternative principal components??" Journal of Econometrics, vol. 146, pp. 318-328. Oct. 2008.
[3] J. Lin and G. Michailidis, "Regularized estimation and testing for high-dimensional multi-block block vector- autoregressive models," Journal of Machine Learning Research, vol. 18, pp. (1188-236, Jan. 2017.
S. Basu, "A system-wide approach to measure connectivity in the financial sector," SSRN Electronic Journal, Aug. 2016.
[5] G. Michailidis and F. d' d'Alché-Bue, "Autoregressive models for gene regulatory network inference: Sparsity, stability and eausality issues," " Mathematical Bioxciences, vol. 246, pp. 326-334, Dec. 2013.
[6] A. Swindlchurst and P. Stoica, "Maximum likelihood methods in radar array signal processing." Proceed- ings of the IEEE, vol. 86, pp. 421-441, Feb. 1998.
Roman, M. Rangaswamy, D. Davis, Q. Zhang, B. Himed, and J. Michels, "Parametric adaptive matched filter for airborne radar applications," JEEE Transactions on Aeroxpace and Electronic Systems, vol. 36, pp. 677-692, Apr. 2000.
[8] K. Sohn, H. Li, and B. Himed, "Parametric GLRT for multichannel adaptive signal detection," " IEFE Transactions on Signal Processing, vol. 55, pp. 5351-5360, Nov. 2007.
[9] P. Wang, H. Li, and B. Himed, "A new parametric GLRT for multichannel adaptive signal detection," " JEEE Transactions on Signal Processing, vol. 58, pp. 317-325, Jan. 2010.
[10] P. Wang, Z. Sahinoglu, M.-O. Pun, and H. Li, "Persymmetrie parametric adaptive matched filter for multichannel adaptive signal detection," JEEE Transactions on Signal Processing, vol. 60, pp. 3322-3328, June 2012.
[11] Y. Gao, H. Li, and B. Himed, "Adaptive subspace tests for multichannel signal detection in auto-regressive disturbance," IEEE Transactions on Signal Processing, vol. 66, pp. 5577-5587, Nov. 2018.
[12] H. Lütkepohl, New Introduction to Multiple Time Series Analysis. Berlin, Germany: Springer Berlin Heidelberg, 2005.
[13] A. Agarwal, S. Negahhan, and M. J. Wainwright, "Fast global convergence of gradient methods for high-dimensional statistical recovery," The Annals of Statistics, vol. 40, pp. 2452-2482, Oct. 2012.
[14] S. N. Negahban, P. Ravikumar, M. J. Wainwright, B. Yu, et al., "A unified framework for sige-dimensionll analysis of m-estimators with decomposable regularizers," Statistical Science, vol. 27, pp. 538-557, Nov. 2012.
[15] V. Chandrasckaran, B. Recht, P. A. Parrilo, and A. S. Willsky, "The convex geometry of lincar inverse problems," Foundations of Computational Mathematics, vol. 12, pp. 805 849, Oct. 2012.
[16] D. Amelunxen, M. Lotz, M. McCoy, and J. Tropp, "Living the edge: Phase transitions in convex programs with random data," Information and Inference, vol. pp. 224-294, June 2014.
[17] S. Oymak, B. Recht, and M. Soltanolkotabi, "Sharp time- data tradeoff's for linear inverse problems," IEEE Transactions on Information Theory, vol. 64, pp. 4129 4158, Nov. 2018
[18] P.-L. Loh and M. J. Wainwright, fliigh-dimensional regression with noisy and missing data: Provable guarantces with nonconvexity." The Annals of Statistics, vol. 40, pp. 1637-1664, June 2012.
[19] F. Han and H. Liu, "Transition matrix estimation in high dimensional time series," in Proceedings of the 30th International Conference on Machine Learning (S. Dasgupta and D. McAllester, eds.). vol. of Proceedings of Machine Learning Research, (Atlanta, Georgia, USA), pp. 172-180, PMLR, June 2013.
[20] S. Basu and G. Michailidis, "Regularized estimation sparse sigh-dimensional time series models," The Annals of Statistics, vol. 43, pp. 1535 1567, Aug. 2015.
[21] Melnyk and Banerjee, "Estimating structured vector autoregressive models." in Proceedings of The 33rd International Conference on Machine Learning (M. F. Balcan and K. Q. Weinberger, eds.), vol. 48 of Proceedings of Machine Learning Research, (New York, New York, USA), pp. 830-839, PMLR, June 2016.
[22] S. Basu, X. Li. and G. Michailidis, "Low rank and structured modeling of high-hiihenn dimensional vector autoregressions." IEEE Transactions Signal Processing, vol. 67, pp. 1207-1222, Mar. 2019.
11

---

[23] P. Netrapalli, N. UN,,S S. Sanghavi, A. Anandkumar, and P. Jain, "Non-convex robust PCA," in Advances in Neural Information Processing Systems (Z. Chahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, eds.), vol. 27, (Montreal, Quebec, Canada), Curran Associates, Inc., Dec. 2014.
[24] X. Yi, D. Park. Y. Chen, and C. Caramanis, "Fast algorithums for robust PCA via gradient descent," in Advances in Neural Information Processing Systems (D. Lee, M. Sugiyama. Luxburg, I. Guyon, and R. Gameett eds.), vol. 29, (Barcelona, Spain), Curran Associates, Inc., Dec. 2016.
[25] Q Gu, Z. W. Wang, and H. Liu, "Low-rank and sparse structure pursuit via altemating minimization." in Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (A. Gretton and C. C. Robert, eds.), vol. 51 of Proceedings of Machine Learning Research, (Cadiz, Spain), pp. 600-609, PML.R, May 2016.
[26] X. Zhang, L. Wang, and Q. Gu, "A unified framework for nonconvex low-rank plus sparse matrix recovery," in Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics (A. Storkey and F. Perez-Cruz, eds.), vol. 84 of Proceedings of Machine Learning Research, (Lanzarote, Canary Islands), pp. 1097-1107, PMLR, Apr. 2018
[27] E. Yang and P. K. Ravikumar, "Dirty statistical models," in Advances in Neural Information Processing Systems (C. J. Burges. L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, eds.), vol. 26. (Lake Tahoe, Nevada, USA), Curran Associates, Inc., Dec. 2013.
[28] X. Lv, Cui, Liu, "A sharp algorithmic analysis of covariate adjusted precision matrix estimation with general structural priors." 2022. [Online]. Available: https://arxiv.orr/abaa 105.00157.
[29] Z. Meng, Eriksson, and Hero, "Learning latent variable gaussian graphical models," in Proceedings of the 31st International Conference on Machine Learning (E. P. Xing and T. Jebara, eds.). vol. 32 of Proce Proceedings of Machine Learning Research, (Bejing, China), pp. 1269- 1277, PMLR, June 2014.
[30] K. Greenewald and A. O. Hero, "Robust Kronecker product PCA for spatio-temporal covariance estimation," IEEE Transactions on Signal Processingg vol. 63, pp. 6368-6378, Aug. 2015.
[31] S. Negahban and M. J. Wainwright, "Restricted strong convexity and weighted matrix completion: Optimal bounds with noise," Journal of Machine Learning Research, vol. 13, pp. 1665-1697, May 2012.
[32] A. Agarwal, S. Negahban, and M. J. Wainwright, "Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions." The Annals of Statisties, vol. 40, pp. 1171-1197, Apr. 2012.
[33] F. Candés and B. Recht, "Exact matrix completion via convex optimization," Communications of the ACM, vol. 55, pp. 111-119, June 2012.
[34] E. J. Candès, X. Li, Y. Ma, and J. Wright, "Robust principal component analysis?," Journal of the ACM, vol. 58, pp. 1-37, May 2011.
[35] J. Duchi, S. Shalch-Shwarts Y. Singer, and Chandra, "Efficient projections onto the 11-ball for learning in high dimensions." in Proceedings of the 25th International Conference on Machine Learning, (Helsinki, Finland), pp. 272-279, Association for Computing Machinery. July 2008
[36] C. Nugent, "S&P 500 stock data." 4.
wwtp:/kaggl....caaaaaaaeeee hata///cmmmuett//aa5500000 2018. Version
[37] C. W. J. Granger, "Investigating causal relations by econometric models and cross-spectral methods," " Econometrica, vol. 37, pp. 424-338, Aug. 1969.
[38] A. Skripnikov and G. Michailidis, "Joint estimation of multiple network Granger causal models," Econo- metrics and Statistics, vol. 10, pp. 120-133, Apr. 2019.
[39] N. Childress, "Bluewhitered.""
4058 bluewhitered, Oct. 2003.
[40] R. Camphell, "ShadedEroorBar"
Mar. 2018.
[41] R. A. González and C. Rojas, "Finite sample deviation and variance bounds for first order autoregressive processes," in ICASSP 2020 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). (Barcelona, Spain). pp. 5380-5384, IEEE, May 2020.
[42] R. Vershynin, High- Dimensional Probability: an Introduction with Applications in Data Science. Cam- bridge Series in Statistical and Probabilistic Mathematics, Cambridge, England: Cambridge University Press, 2018
12

---

[43] N. M. N. Boris S. Mordukhooich,, An Easy Path Convex Analysis and Applications. San Rafael, CA. USA: Morgan & Claypool Publishers, 2013.
[44] S. Dirksen, "Tail bounds via generic chaining," Electronic Journal of Probability, vol. 20, pp. 1-29, May 2015.
[45] M. Talagrand, Upper and Lower Bounds for Stochastic Processex. Berlin, Germany: Springer, 2014.
[46] M. Talagrand, The Generic Chaining. Berlin, Germany: Springer, 2005.
[47] M. Rudelson and R. Vershynin, "Hanson- Wright incquality and sub-gaussian concentration," Electronic Communications in Probability, vol. 18, pp. 1-9, Oct. 2013.
[48] V. de Peña, "A general class exponential incqualities for martingales and ratios," The Annals of Probability, vol. 27, pp. 537-564, Jan. 1999.
[49] M. J. Wainwright, High DimeeniDmmsii Statistics. Cambridge, England: Cambridge University Press, 2019.
[50] Sobral, Bouwmans,
Zahzah, "Lrslibrary: Low-rank sparse tools background modeling and subtraction vidcos," in Robust Low-Rank and Sparse Matrix Decomposition: Applications in Image and Video Processing, Boca Raton, Florida, USA: CRC Press, Taylor and Francis Group 2015.
13


Reviews:
[{"review_id": "y2YZA7tB1Cj", "reviewer": "Reviewer_SbHr", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n\nThe 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. \n\nQuality:\n\nThe 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. \n\nClarity:\n\nThe 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?\n\nSignificance: \n\nUsing 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.\n\n[1] I. Melnyk and A. Banerjee. Estimating Structured Vector Autoregressive Models. In International Conference on Machine Learning, pages 830–839, June 2016. \n\n[2] Q. Gu and A. Banerjee. High dimensional structured superposition models. In Advances in Neural Information Processing Systems, pages 3684-3692, 2016.\n\n[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.\n\n********************* Post-rebuttal comments *********************\nI 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "pZV4lEPNTNm", "reviewer": "Reviewer_ZMT4", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- The paper focuses on the special case of VAR models of lag 1 with serially uncorrelated Gaussian errors.\n- 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.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "lUTTKwcinW0", "reviewer": "Reviewer_Ptje", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nThe main limitations of the paper:   \n1) 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. \nBaseline 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. \n\n2) 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. \n\nMinor comments: \n1) 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. \n2) 'studied by numerous literatures' - awkward. \n3) Please take a look at references for some clean-up e.g. pca->PCA .. S&p -> S&P, e.t.c. , ref[40], ...\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "bDTRCTtSXRI", "reviewer": "Reviewer_CH7C", "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). ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\n2) 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. \n\n3) Theorem 2 and Corollary 3 from [18] also provides optimization error. This should be discussed.  \n\n4) 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\n\n==========\nThanks for the response. I maintain my score.\n\nTo 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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "none (to this reviewers knowledge) ", "review_text": "", "extra_scores": {"ethical_concerns": "none (to this reviewers knowledge) ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "TEptYQmsq3", "reviewer": "Reviewer_cNh8", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n\n- 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.\n\n\n\n- 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:\n\n- Sentence seems to be incomplete: page 2, line 72, ``when the transition ...\"\n\n- Incomplete sentence on page 3, line 86: ``we require ...\"\n\n- cone(.) is not defined but used on page 4, line 108\n\n- The set $S_F$ used in equation 15, page 4, but not defined before (Same for $S_2$ in equation 35 in the supplement).\n\n- Which norm on the covariance of error terms does appear in equation 18? Is it the operator norm?\n\n- The notation script P, i.e. $\\mathcal{P}$ (projection) is used in equation 5 on page 3, but not defined before.\n\n\n\n\n\n\n- 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.\n\n\n\n- 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.\n\n\n\n- 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).\n\n- It is not clear why the inequality in equation 18 holds, please elaborate.\n\nReference:\n\nHsu, D., Kakade, S. M., \\& Zhang, T. (2011). Robust matrix decomposition with sparse corruptions. IEEE Transactions on Information Theory, 57(11), 7221-7234.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "around 8"}, "extra_text": {}}]

Author rebuttal:

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)