Performance of Empirical Risk Minimization For Principal Component Regression
Christian Brownlees Guðmundur Stefán Guðmundsson Yaping Wang





















defnDefinition
propProposition
*prop-nonumberProposition
lemmaLemma
thmTheorem
*thm-nonumberTheorem
corCorollary

*asmredef*

asmredef[2]
 
  
  
  @edefcurrentlabelA.#1*
 
 
  
 



mytheorem
  
  
  
  0pt
  
  .
   
  #1.#2 (#3)
mytheorem

asmA
asmA.






 
 

[#1]#2footnote[#2]
    
      
Performance of Empirical Risk Minimization 
 For Principal Component Regression 
    Christian Brownlees^†,* Guðmundur Stefán Guðmundsson^ Yaping Wang^†
    September 9, 2024
================================================================================



§ ABSTRACT 

This paper establishes bounds on the predictive performance of empirical risk minimization for principal component regression.

Our analysis is nonparametric, in the sense that the relation between the prediction target and the predictors is not specified.
In particular, we do not rely on the assumption that the prediction target is generated by a factor model.
In our analysis we consider the cases in which the largest eigenvalues of the covariance matrix of the predictors grow linearly in the number of predictors (strong signal regime)
or sublinearly (weak signal regime).

The main result of this paper shows that empirical risk minimization for principal component regression is consistent for prediction and, under appropriate conditions, it achieves optimal performance (up to a logarithmic factor) in both the strong and weak signal regimes.

Keywords: empirical risk minimization, principal component regression, time series, oracle inequality

JEL: C13, C14, C22, C55



[0]

^† Department of Economics and Business, Universitat Pompeu Fabra and Barcelona GSE;

e-mail: , .

^ Department of Economics and Business Economics, Aarhus University; 

e-mail: .

^* Corresponding author. 
 
We have benefited from discussions with Gabor Lugosi, David Rossell and Piotr Zwiernik.

Christian Brownlees acknowledges support from the Spanish Ministry of Science and Technology (Grant MTM2012-37195);
the Ayudas Fundación BBVA Proyectos de Investigación Cientìfica en Matemáticas 2021;
the Spanish Ministry of Economy and Competitiveness through the Severo Ochoa Programme for Centres of Excellence in R&D (SEV-2011-0075).

Guðmundur Stefán Guðmundsson acknowledges financial support from the 
Danish National Research Foundation (DNRF Chair grant number DNRF154).





§ INTRODUCTION


Principal component regression (PCR) is a regression methodology with a long and well established tradition that can be traced back to at least <cit.> and <cit.>. 
In a nutshell, PCR consists in forecasting a prediction target of interest on the basis of the principal components extracted from a potentially large set of predictors.
PCR is a popular tool for forecasting in macroeconomics where it is documented to perform favourably relative to a number of competing approaches <cit.>.

In this paper we study the properties of PCR from a learning theory perspective.
Our main contribution consists in establishing nonasymptotic prediction performance guarantees for PCR. 
Our main result may be interpreted as a nonasymptotic analogue of classic asymptotic results on the prediction properties of PCR obtained in <cit.> <cit.>.  
An important feature of our analysis is that we treat PCR as a regularization procedure and we do
not assume that the data are generated by a factor model.
In particular, as is customary in learning theory, the relation between the prediction target and the predictors is not specified.
That being said, as the factor model feinschmecker will recognize, our framework relies on assumptions and proof strategies analogous to the ones used in the factor model literature.
In particular we build upon classic contributions such as <cit.>, <cit.>, <cit.> and <cit.> among others.

PCR may be described as a two-step procedure.

Let 𝒟 = { (Y_t,  X_t')' }_t=1^T be a stationary sequence of zero-mean random vectors 
taking values in 𝒴×𝒳⊂ℝ×ℝ^p.
The goal is to forecast the prediction target Y_t using the 
p-dimensional vector of predictors X_t=(X_1 t,…,X_p t)'.

The first step of PCR consists in computing the T × K principal components matrix P = ( P_1, …,  P_T)' associated with 
the T × p predictor matrix X = ( X_1, …,  X_T)', for some appropriate choice of K.

This may be defined as the solution of the constrained least squares problem 

    (  B ,  P ) = min_ B ∈ℝ^p × K
     P ∈ℝ^T × K X -  P  B' _F^2 
    	  s.t. 1 T P'  P =  I_K, 1  p B'  B  is diagonal,

where ·_F denotes the Frobenius norm.
As is well known, P is given by √(T) times the first K eigenvectors of the matrix 
X  X'. 
It is useful to remark here that the principal components allow us to express the vector of predictors X_t as a linear combination of the matrix of coefficients B with the K principal components P_t plus a residual vector u,  
that is

    X_t =  B P_t +  u_t  ,

where u_t =  X_t -  B P_t.
The second step of PCR consists in computing the K× 1 least squares coefficients vector ϑ̂ associated with the regression of the T× 1 target variable vector Y = (Y_1, …, Y_T)' on the principal components matrix P.
This is the solution to the least squares problem

    ϑ̂ = min_ϑ∈ℝ^K  Y -  Pϑ^2_2  ,

where ·_2 denotes the Euclidean norm. It is straightforward to check that ϑ̂ = P'  Y / T.

PCR may be interpreted as regularized empirical risk minimization.[
We remark that in this paper we use the expression “empirical risk minimization for principal component regression” only for simplicity.
A more appropriate name for the procedure we study would be “regularized empirical risk minimization based on principal component analysis”.]
Consider the class of prediction rules indexed by θ∈ℝ^p given by f_θ t = θ '  X_t.
Then PCR can be cast as the regularized empirical risk minimization problem given by

    θ̂_PCR∈min_θ∈ℝ^p  R_T(θ)
    	   s.t.   V_R' θ =  0  ,

where  

    R_T(θ) = 1  T∑_t=1^T ( Y_t - f_θ t )^2

is the empirical risk and  

    V_R  = ( v_K+1 , … , v_p )  ,

where v_i is the eigenvector associated with the i-th largest eigenvalue of the sample covariance matrix of the predictors Σ =  X' X/T.
The vector θ̂_PCR defined in (<ref>) is the solution to a least squares problem subject to a set of linear constraints.
It is straightforward to verify that 



f̂^PCR_t = θ̂_PCR' X_t  = ϑ̂' P_t,
which implies that the forecasts produced by PCR may be equivalently expressed as linear forecasts based on constrained least squares.

One of the main objectives of learning theory is to obtain a bound on the predictive performance of the ERM relative to the optimal risk that can be achieved within the given class of prediction rules.
We define the risk of a prediction rule as R( θ ) = 𝔼[   ( Y_t - f_θ t )^2 ].
The optimal risk is defined as the risk of a prediction rule associated with a θ^* such that

    R( θ^* ) = min_θ∈ℝ^p𝔼[ ( Y_t - f_θ t )^2 ]  .


The conditional risk of PCR is used to measure predictive performance. This is given by

    R( θ̂_PCR )  
    	= 𝔼[ . ( Y_t - f̂^PCR_t )^2 | θ̂_PCR = θ̂_PCR(𝒟) ]  ,

where (Y_t, X_t)' in (<ref>) denotes an element of the process assumed to be drawn independently of 𝒟.

The performance measure in (<ref>) can be interpreted as the risk of the ERM obtained from the “training” sample 𝒟 over the “validation” observation (Y_t, X_t)'.

Then our aim is to find a pair (B_T(p,K),δ_T) such that B_T(p,K) → 0 and δ_T→ 0 as T →∞ for which 

    R( θ̂_PCR ) ≤ R(θ^*) + B_T(p,K)

holds with probability at least  1 - δ_T for any T sufficiently large.
The inequality in (<ref>) is commonly referred to as an oracle inequality.
Oracle inequalities such as (<ref>) provide non-asymptotic guarantees on the performance of the ERM and 
imply that the ERM asymptotically performs as well as the best linear predictor.
We remark that the performance measure in (<ref>) allows us to keep our analysis close
to the bulk of the contributions in the learning theory literature (which typically focus on the analysis of i.i.d. data) and facilitates comparisons.
We remark that <cit.> and <cit.> consider 
alternative performance measures such as the conditional out-of-sample average risk of the ERM, 
which has a more attractive interpretation for time series applications. 
It turns out that these alternative measures lead to essentially the same theoretical analysis 
at the expense of introducing additional notation.
We therefore focus on the performance measure defined in (<ref>) for clarity.

This paper is related to various strands of the literature.

First, the vast literature on approximate factor models, principal component analysis and spiked covariance models, 
which includes <cit.>, <cit.>,  <cit.>, <cit.>, <cit.>, <cit.>, <cit.>, <cit.>, <cit.>, <cit.> and <cit.>.

In particular, this work is close to the important contribution of <cit.> 
that studies the properties of a large class of high-dimensional models, which includes factor models, 
and establishes results on the predictive performance of such a class.
Second, it is related to the literature on the small-ball method, which includes <cit.>, <cit.>, <cit.> and <cit.>.

Third, the literature on empirical risk minimization for linear regression, 
which includes <cit.> and <cit.> among others.
In particular, our contribution is close to the subset of the literature that deals with dependent data, 
as in <cit.>.

The rest of the paper is structured as follows.
Section <ref> introduces additional basic notation, assumptions and preliminary results.
Section <ref> contains the main result of the paper and its proof is outlined in Section <ref>.
Concluding remarks follow in Section <ref>.
All the remaining proofs are given in the appendix.



§ NOTATION, PRELIMINARIES AND ASSUMPTIONS
 

In this section we lay out the assumptions required for our analysis.
Our assumptions may be interpreted as the union of standard conditions employed in the approximate factor model literature <cit.> and conditions employed in the learning literature based on the small-ball method <cit.>.


We introduce some basic notation.
For a generic vector x ∈ℝ^d we define x _r as [ ∑_i=1^d |x_i|^r ]^1/r for 1 ≤ r < ∞ and max_i=1,…,d |x_i| for r=∞.
For a generic random variable X ∈ℝ we define X _L_r as [𝔼 ( |X|^r ) ]^1/r for 1 ≤ r < ∞ and inf{ a : ℙ( |X|> a ) = 0 } for r=∞.
For a positive semi-definite matrix 𝐌 we use 𝐌^1/2 to denote the positive semi-definite square root matrix of 𝐌 and 𝐌^ -1/2 to denote the generalized inverse of 𝐌^1/2.


For a generic matrix 𝐌 we use 𝐌_2 to denote the spectral norm of 𝐌.

We begin with a preliminary lemma that establishes the population analogue of the principal components decomposition of the prediction vector X_t introduced in (<ref>).



Let X_t be a zero-mean p-dimensional random vector with Σ = 𝔼( X_t  X_t').
For any K ∈{1, …  p}, define Λ_K = diag(λ_1,…,λ_K), Λ_R = diag(λ_K+1,…,λ_p), V_K = ( v_1,…, v_K) and V_R = ( v_K+1,…, v_p)
where λ_1, …, λ_p and v_1, …,  v_p denote the sequence of eigenvalues of Σ in a non-increasing order and the corresponding sequence of eigenvectors.

Then, (i) it holds that

    X_t = 𝐁 P_t +  u_t  ,

where 𝐁 =  V_K Λ_K^1/2, P_t = Λ_K^-1/2 V_K'  X_t and u_t =  V_R ( V_R'  V_R)^-1 V_R'  X_t with
𝐁' 𝐁 diagonal, 𝔼 (  P_t  P_t' ) =  I_K, 𝔼( u_t  u_t') =  V_R Λ_R  V_R' and 𝔼 (  P_t u_t' ) =  0_K × p.
(ii) Let θ^* ∈ℝ^p be the vector of coefficients of the best linear predictor of Y_t based on X_t. Then, it holds that 

    X_t'θ^* =  P_t ' ϑ^* +  u_t ' γ^* ,

where ϑ^* = Λ_K^1/2 V_K' θ^* and γ^* =  V_R ( V_R'  V_R)^-1 V_R' θ^*.


Parts (i) of Lemma <ref> states that X_t can decomposed into a linear combination 
of the matrix of coefficients 𝐁 with the random vector P_t plus the residual random vector u_t, where P_t and u_t are orthogonal.
We call P_t the population principal components and u_t the idiosyncratic component.
Part (ii) implies that the best linear predictor for Y_t can be alternatively represented
as a function of the population principal components P_t and the idiosyncratic component u_t with the coefficient vectors ϑ^* and γ^*.
Note that since P_t and u_t are orthogonal, ϑ^* may be interpreted as the best linear predictor based on the population principal components P_t.
We remark that, clearly, in the definitions of u_t and γ^* the matrix V_R ( V_R'  V_R)^-1 V_R' may be simplified to V_R  V_R' but we prefer to express it in this way to emphasize that this is a projection matrix.
Last note that the decomposition established in part (ii) holds for any vector in ℝ^p but for our purposes it suffices to focus on the vector of coefficients of the best linear predictor.
Also notice that the vector of coefficients of the best linear predictor may not be unique, but this raises no issues in our setup.

We lay out the assumptions of our analysis.
We say that the d-dimensional random vector U is sub-Gaussian with parameters C_m > 0 if, 
for any ε>0, it holds that

    ℙ( sup_ v :  v _2=1 |  v' U | > ε) ≤exp( -C_m ε^2 )  .

For a univariate random variable U this is equivalent to ℙ( | U | > ε ) ≤exp( -C_m ε^2 ).

[Distribution]
(i) There exists a positive constant C_m such that Y_t, Y_t -  P_t'ϑ^* and Z_t=Σ^-1/2 X_t with Σ = 𝔼( X_t  X_t') are sub-Gaussian with parameter C_m.
(ii) There exists a constant C_Z and a p-dimensional spherical random vector S such that for any B ∈ℬ(ℝ^p) it holds that ℙ(  Z_t ∈ B ) ≤ C_Z ℙ(  S ∈ B ),
where the spherical random vector S is such that its density exists and the marginal densities of its components are bounded from above.


Part (i) states that the tails of the data decay exponentially. 
More precisely it assumes that the prediction target Y_t, the prediction error of the best linear predictor based on the principal components P_t given by Y_t -  P_t'ϑ^* and the standardized predictors Z_t have sub-Gaussian tails.
We remark that such a condition is fairly standard in the analysis of large-dimensional factor models <cit.>.
We also remark that the sub-Gaussian condition may be replaced by a sub-Weibull condition at the expense of longer proofs <cit.>.
Part (ii) is a regularity condition on the density of the standardized predictors Z_t
that is required to establish upper bounds on the probability of a certain event associated with the vector 
of predictors X_t in one of the intermediate propositions of our analysis.
The same condition is assumed in <cit.>.

Let ℱ_-∞^t and ℱ_t+l^∞ be the σ-algebras generated by { (Y_s,  X_s')': -∞≤ s ≤ t} and { (Y_s,  X_s')': t + l ≤ s ≤∞} respectively for some t ∈ℤ and define the α-mixing coefficients 

    α(l) = sup_A ∈ℱ_-∞^t, B ∈ℱ_t+l^∞| ℙ(A ∩ B ) - ℙ(A) ℙ(B) |.


[Dependence]
There exist constants C_α>0 and r_α>0 such that the α-mixing coefficients satisfy α(l) ≤exp( -C_α l^r_α ). 


<ref> states that the process { (Y_t,  X_t')'} has geometrically decaying strong mixing coefficients,
which is a fairly standard assumption in the analysis of large dimensional time series models <cit.>.

[Eigenvalues]
There is an integer K ∈{1,…,p}, a constant α∈ (1/2,1]
and a sequence of non-increasing nonnegative constants c_1,…,c_p with c_K>0 
such that, 
λ_i = c_i p^α for i=1,…,K, 
λ_i = c_i for i=K+1,…,p.


<ref> states that the first K eigenvalues of the covariance matrix Σ diverge as the cross-sectional dimension p becomes large.
The rate of divergence is determined by α. We distinguish between two regimes that depend on the value of this constant.
When α=1 we say that we are in the strong signal regime, which is analogous to (classic) 
factor models with pervasive factors <cit.>.
When α∈ (1/2,1) we say that we are in the weak signal regime, which is analogous to 
weak factor models <cit.>.
We remark that this assumption is weaker than <cit.>, which only allows for strong signals.
We also point out that K here is assumed to be known and that there is a large literature devoted to the estimation of this quantity <cit.>.

Last, it is important to emphasize that the assumption allows for the non-diverging eigenvalues 
of Σ to be zero, so our framework allows Σ to be singular.
 




















































[Number of Predictors and Principal Components]
(i) There are constants C_p>0 and r_p ∈ (0,r_p) such that p = ⌊ C_p T^r_p⌋ where r_p = r_α∧1  r_α+1  r_α- α.
(ii) There are constants C_K>0 and r_K ∈ [0,r_K) such that K = ⌊ C_K T^r_K⌋ where r_K = 1-r_p( 1- α) ∧1 3 + 2  r_α.


<ref> states that the number of predictors and the number of principal components are allowed to increase as a function of the sample size T.
The rate of growth of these quantities depends on the rate of decay of the strong mixing coefficients (as measured by r_α) and the strength of the signal (as measured by α).
The less dependence and the stronger the signal, the larger the numbers of allowed predictors 
and principal components.
The assumption allows the number of predictors to be larger than the sample size T whereas the number of principal components is at most T^1/3 (up to a proportionality constant).
It is important to emphasize that when the signal is weaker, 
the maximum rate of growth of the number of predictors is smaller.
The condition on the maximum rate of growth of the number of predictors r_p is analogous to condition (9) in <cit.>, who study the properties of factor models in the weak signal regime.

[Identification/Small-ball] 
There exist positive constants κ_1 and κ_2 such that, 
for each θ_1, θ_2 ∈ℝ^p, and for each t = 1, …, T

    ℙ( | f_θ_1 t - f_θ_2 t | 
        ≥κ_1  f_θ_1 t - f_θ_2 t_L_2) ≥κ_2  .



<ref> is the so-called small-ball assumption, 
and it is stated here as it is formulated in <cit.>.
This assumption can be interpreted as an identification condition.
If we define δ=(θ_1-θ_2) then the condition is equivalent to 
ℙ( | δ'  X_t | ≥κ_1 δ'  X_t _L_2) ≥κ_2,
which can be seen as requiring the random variable δ'  X_t to not have excessive mass 
in a neighbourhood around zero. 
We remark that the constants κ_1 and κ_2 measure the strength of the identification 
in the sense that the larger the value of these constants the stronger the identification condition.
We also remark that <cit.> discuss conditions that imply <ref>. 



§ PERFORMANCE OF EMPIRICAL RISK MINIMIZATION


We now state our main result on the performance of empirical risk minimization.


Suppose <ref>–<ref> are satisfied.

Then for any η>0 there exists a constant C>0 such that, for any T sufficiently large, 

    R( θ̂_PCR ) 
    ≤ R( θ^*) 
    + (θ^*)'  V_R Λ_R  V_R' θ^* 
    + C [  1  p^2α-1 + ( p  T p^α)^2 p^2  r_α + K  T ] log(T),

holds with probability at least 1-T^-η.


The theorem establishes a regret bound on the excess risk of PCR relative to the best linear predictor that can be obtained on the basis of the predictors X_t.
The gap is made up of two terms. The first can interpreted as the approximation error of PCR and the second as the estimation error.
The approximation error measures the gap between the performance of the best linear predictor based on the population principal components P_t and the best linear predictor based on the predictors X_t.
The estimation error measures the gap between the performance of PCR relative to the best linear predictor 
based on the population principal components P_t.

A number of additional remarks on Theorem <ref> are in order.
First, it is insightful to provide an alternative representation of the approximation error of PCR. This may be equivalently expressed as

    (θ^*)'  V_R Λ_R  V_R' θ^* = Λ^1/2_R  V_R' θ^* ^2_2
    	= Λ^1/2_R  V_R'  V_R (  V_R'  V_R)^-1 V_R' θ^* ^2_2 = (γ^*)'  V_R Λ_R  V_R' γ^*  .

This highlights that the approximation error of PCR is small when the projection of the best linear predictor 
θ^* on the subspace spanned by the population eigenvectors v_K+1, …,  v_p is small.
Differently put, if the contribution of the idiosyncratic component vector u_t is negligible then PCR has a negligible approximation error.
Clearly, when γ^* =  0 the best linear predictor based on X_t coincides with the best linear predictor based on P_t and the approximation error is zero.

Second, it is interesting to provide some comments on the behaviour of the approximation error.
Under the rate conditions of <ref> the approximation error is asymptotically negligible as T →∞.
We remark that the condition p /( p^α T) → 0 as T→∞ is also required by <cit.> in the analysis of approximate weak factor models. The approximation error is also influenced by the degree of persistence in the data, as measured by r_α, and in particular the more dependent the data are the slower the convergence of the approximation error to zero. We remark that the results of <cit.>, among others, do not depend on the degree of persistence of the data. This is due to the fact that their analysis relies on higher level conditions that imply sharp rates of convergence of certain key estimators in the analysis. 
It is also interesting to note that the approximation error is made up of three terms that can be easily associated with the different estimation problems embedded in PCR.
The first two terms capture the estimation error of the principal components whereas the third one 
can be interpreted as the estimation error the principal component regression if the population principal components were observed.

Last, an important question concerning the approximation error is whether the rate obtained for it 
in the theorem is optimal. 
We provide insights on this question below in Section <ref>.






 §.§ Optimal Performance


A natural question that arises upon inspection of Theorem <ref> is whether the learning rate for 
the approximation error is, in some appropriate sense, optimal.
We compare the learning rate established by the theorem with the optimal learning rate that could 
be achieved if the population principal components were observed.
In this case it is well known that the optimal rate is of the order K/T <cit.>, 
which is achieved by the least squares estimator based on the population principal components. 
In this section we assume that the approximation error is zero for ease of exposition.

For a given choice of the signal strength α, degree of dependence r_α and 
the rate of growth of the number of principal components r_K,
it is straightforward to verify that the optimal rate can be recovered in Theorem <ref>
provided that 

    1-r_K  2α-1 < 1+r_K  2-2α+2/r_α ,

and that the rate of growth of the number of parameters allowed is such a scenario is 

    r_p ∈[ 1-r_K  2α-1 , 1+r_K  2-2α+2/r_α]  .


In particular we note that the optimal rate can be achieved in the both the strong signal (α=1),
and the weak signal (α<1) cases, provided that α > 2/3.
The larger the values of α, r_α and r_K, 
the larger the range of admissible growth rates for the number of predictors r_p.

It is interesting to provide concrete examples of these conditions.
In the presence of a strong signal (α=1), a fixed number of principal components (r_K=0) and 
independent data (r_α = ∞)[The proofs of this manuscript assume that r_α is finite.] we obtain that 

    R(θ̂) - R(θ^*) ≤ 
    C ( 1/p 
        + 1/T^2
    	+ K/T) log (T)
        = O( K/Tlog(T) ),

when r_p ∈ [1,∞).
In the presence of a weak signal (α<1), a fixed number of principal components (r_K=0) 
and independent data (r_α = ∞) we obtain that 

    R(θ̂_PCR) - R(θ^*) =
    	O ( 1/p^2 α - 1 
        + p^2 - 2 α/T^2
    	+ K/T) log (T)
        = O( K/Tlog(T) ),

when r_p ∈ [ 1/(2α-1) , 1/(2-2α) ]. 
In particular when α = 3/4 the rate of growth of the number of parameters required 
to achieve optimal performance is r_p=2.



§ PROOF OF MAIN RESULT


We introduce some additional notation.
In this section and in the appendices we use the subscript s to denote the index of an
observation in the training sample 𝒟 and the subscript t to denote the index of 
a validation observation.
Also, for some random variable X we use X _L_2 to denote √(𝔼( X^2 | 𝒟 ) ).

The proof of Theorem <ref> begins with a decomposition of an upper bound of the excess risk of the empirical risk minimizer.
Define the approximate rotation matrix H = Λ_K ^-1/2 V_K'  V_K Λ_K ^1/2 <cit.>
and the infeasible PCR estimator ϑ̃ = min_ϑ∈ℝ^K 1  T∑_t=1^T ( Y_t -  P_t'ϑ )^2.
The following lemma provides a useful bound for the excess risk.
We remark that the lemma only requires stationarity and finite variance. 



Suppose that { (Y_t, X_t')' } is a stationary sequence taking values in 𝒴×𝒳∈ℝ×ℝ^p such that 
𝔼(Y_t^2) < ∞ and 𝔼(X_i t^2) < ∞ for all i = 1, …, p.

Then it holds that 

    R( θ̂_PCR ) - R( θ^*) ≤ 
    	2 max_1 ≤ s ≤ T{ Y^2_s }𝔼(  P_t -  H  P_t ^2_2 | 𝒟 ) 
    	+ 4 ϑ̃ -  H ' ϑ̂^2_2 
    	+ 4 ϑ^* - ϑ̃^2_2 
    	+ 2  u_t'γ^* ^2_L_2 .



Lemma <ref> implies that in order to control the excess risk of PCR it suffices to provide appropriate bounds on the four terms on the right hand side of (<ref>).
The following four propositions establish such bounds.

The first two propositions control the terms 
𝔼(  P_t -  H  P_t ^2_2 | 𝒟 ) and 
ϑ̃ -  H ' ϑ̂^2_2.
We remark that these two terms capture the risk of PCR that is due to the estimation of the principal components.
The proof of the propositions is based on standard arguments from the approximate factor model literature <cit.>.



Suppose <ref>–<ref> are satisfied. 

Then for any η>0 and any T sufficiently large, 

    𝔼 (  P_t -  H  P_t ^2_2 | 𝒟 )
    ≤c_K+1 2 c_K^21  p^2α-1,

holds with probability at least 1-T^-η.




Suppose <ref>–<ref> are satisfied. 

Then for any η>0 there is C>0 such that, for any T sufficiently large, 

    ϑ̃ -  H ' ϑ̂^2_2 
    ≤ C { K  T  + log (T) T    + [ (p + log(T) )^r_α +1
     r_α p^αT]^2  + 1  p^2α}log(T),

holds with probability at least 1-T^-η.


The next proposition controls the term ϑ^* - ϑ̃^2_2.
We remark that this term may be interpreted as the risk of the least squares estimator of PCR based on the population principal components.
The proof of the proposition is based on the so-called small-ball method,
which is the same proof strategy used in <cit.>.



Suppose <ref>–<ref> are satisfied.

Then for any η>0 there is a C>0 such that, for any T sufficiently large, 

    ϑ^* - ϑ̃^2_2≤ C K log (T)  T,

holds with probability at least 1-T^-η.


The following proposition controls the error u_t'γ^* ^2_L_2, which can be interpreted as the approximation error of PCR.



Suppose <ref> and <ref> are satisfied.

Then it holds that  

    u_t'γ^* ^2_L_2 = (θ^*)'  V_R Λ_R  V_R' θ^*  .



The claim of Theorem <ref> follows from Propositions <ref> to <ref> together with  the implication rule, the C_r inequality, the union bound and the fact that 
the sub-Gaussian assumption on Y_t (<ref>) implies that for each η>0 there is a C>0 such that 

    ℙ( max_1 ≤ s ≤ T{ Y^2_s }≤ C log(T) ) ≤ 1-T^-η .




§ CONCLUSIONS


This paper establishes predictive performance guarantees for principal component regression.

Our analysis has a number of highlights.
First, the analysis we carry out is nonparametric, 
in the sense that the relation between the prediction target and the predictors is not specified and,
in particular, we do not assume that the prediction target is generated by a factor model.
Second, our framework considers both the cases in which the largest eigenvalues of the covariance matrix 
of the predictors diverge linearly in the number of predictors (strong signal regime) 
or sublinearly (weak signal regime).

A highlight of our results is that we show that, under appropriate conditions, PCR achieves optimal performance (up to a logarithmic factor) in both the strong signal and weak signal regimes.





§ PROOFS









We recall that Σ = (  V_K Λ_K  V_K' +  V_R Λ_R  V_R')
where V_K = ( v_1,…, v_K), V_R = ( v_K+1,…, v_p), Λ_K = diag(λ_1,…,λ_K) and Λ_R = diag(λ_K+1,…,λ_p).
Analogously, we have that Σ = (  V_K Λ_K  V_K' +  V_R Λ_R  V_R')
where V_K = (v̂_1,…,v̂_K), V_R = (v̂_K+1,…,v̂_p), Λ_K = diag(λ̂_1,…,λ̂_K) and Λ_R = diag(λ̂_K+1,…,λ̂_p).



(i) We have that 𝐁 P_t +  u_t =  V_K  V_K'  X_t + (  I_p -  V_K  V_K')  X_t =  X_t.
We have that 𝐁' 𝐁  = Λ_K^1/2 V_K' V_K Λ_K^1/2  = Λ_K,
that
𝔼 (  P_t  P_t' ) = Λ_K^-1/2 V_K' (  V_K Λ_K  V_K' +  V_R Λ_R  V_R')  V_K Λ_K^-1/2 =  I_K,
𝔼 (  u_t  u_t' ) =  V_R  V_R' (  V_K Λ_K  V_K' +  V_R Λ_R  V_R')  V_R  V_R'=  V_R Λ_R  V_R',
and that
𝔼  (  P_t u_t' ) = Λ_K^-1/2 V_K' ( V_K Λ_K  V_K' +  V_R Λ_R  V_R' )  V_R  V_R' =  0_K × p. 
(ii) Note that X_t'θ^* =  P_t' 𝐁' θ^* +  u_t'θ^*
and that P_t' 𝐁' θ^* =  P_t'Λ^1/2_K  V_K' θ^* =  P_t'ϑ^* and 
u_t'θ^* =  u_t' ( I_p -  V_K ( V_K'  V_K)^-1 V_K') θ^* =  u_t' γ^* since I_p -  V_K ( V_K'  V_K)^-1 V_K' is idempotent.




Consider the excess risk decomposition given by

    R( θ̂_PCR ) - R( θ^*) 
    	    =  Y_t -  P'_t ϑ̂^2_L_2 -  Y_t -  P'_t  H ' ϑ̂^2_L_2
        +  Y_t -  P'_t  H ' ϑ̂^2_L_2 -  Y_t -  P'_t ϑ̃^2_L_2
        +  Y_t -  P'_t ϑ̃^2_L_2 -  Y_t -  P'_t ϑ^* ^2_L_2
        +   Y_t -  P'_t ϑ^* ^2_L_2 -  Y_t -  X_t' θ^* ^2_L_2 .

The projection theorem, the fact (a+b)^2≤ 2 a^2 + 2 b^2, the fact 𝔼( P_t  u_t' ) =  0 and the Cauchy-Schwarz inequality imply 

    Y_t -  P'_t ϑ̂^2_L_2 -  Y_t -  P'_t  H ' ϑ̂^2_L_2
          =  Y_t -  X'_t θ^* +  X'_t θ^* -  P'_t ϑ̂^2_L_2 -  Y_t -  X'_t θ^* +  X'_t θ^*-  P'_t  H ' ϑ̂^2_L_2
          =  X'_t θ^* -  P'_t ϑ̂^2_L_2 -  X'_t θ^*-  P'_t  H ' ϑ̂^2_L_2
    
    	
    	
    	
    	     ≤ 2  P'_t ϑ^* -  P'_t  H ' ϑ̂ +  u_t'γ^* ^2_L_2 
    	+ 2  P'_t  H ' ϑ̂ -  P'_t ϑ̂^2_L_2 
    	-  P'_t ϑ^*-  P'_t  H ' ϑ̂^2_L_2 -  u_t'γ^* ^2_L_2
          =  P'_t ϑ^* -  P'_t  H ' ϑ̂^2_L_2 
    	+ 2  P'_t  H ' ϑ̂ -  P'_t ϑ̂^2_L_2 +  u_t'γ^* ^2_L_2
         ≤ 
    	2  P'_t ϑ^* -  P'_t ϑ̃^2_L_2 
    	+ 2  P'_t ϑ̃ -  P'_t  H ' ϑ̂^2_L_2 
    	+ 2  P'_t  H ' ϑ̂ -  P'_t ϑ̂^2_L_2 +  u_t'γ^* ^2_L_2
         ≤  
    	2 ϑ^* - ϑ̃^2_2 
    	+ 2 ϑ̃ -  H ' ϑ̂^2_2 
    	+ 2 ϑ̂_2^2 𝔼(  P_t -  H  P_t ^2_2 | 𝒟 )  +  u_t'γ^* ^2_L_2 .

To see how the projection theorem applies to the second equality note that P'_t ϑ̂ =  X_t'  V_K Λ^-1/2_K ϑ̂
and P'_t  H ' ϑ̂ =  X'_t  V_K Λ^-1/2_K  H ' ϑ̂.
Furthermore, we have that 

    ϑ̂_2 = 1 T P'  Y  _2 
    ≤√(1  T) P' _2 √(1 T) Y  _2 
    = √( 1  T) Y  _2  ≤max_1 ≤ s ≤ T |Y_s|  .

Next, the projection theorem, the Cauchy-Schwarz inequality and the inequality 2 a b ≤ a^2 + b^2 imply that

    Y_t -  P'_t  H ' ϑ̂^2_L_2 -  Y_t -  P'_t ϑ̃^2_L_2
          =   Y_t -  P'_t ϑ^* +  P_t' ( ϑ^* -  H ' ϑ̂ ) ^2_L_2 -  Y_t -  P'_t ϑ^* +  P_t' ( ϑ^* - ϑ̃ )   ^2_L_2
          =   P_t' ( ϑ^* -  H ' ϑ̂ ) ^2_L_2 -  P_t' ( ϑ^* - ϑ̃ )   ^2_L_2
          = 𝔼[ . [  P_t' ( ϑ^* -  H ' ϑ̂ ) -  P_t' ( ϑ^* - ϑ̃ ) ]
    	[  P_t' ( ϑ^* -  H ' ϑ̂ ) +  P_t' ( ϑ^* - ϑ̃ ) ] | 𝒟] 
          = 𝔼[ . [  P_t' ( ϑ̃ -  H ' ϑ̂ ) ]
    	[  P_t' ( ϑ^* -  H ' ϑ̂ + ϑ^* - ϑ̃ ) ] | 𝒟] 
          = 𝔼[ . [  P_t' ( ϑ̃ -  H ' ϑ̂ ) ]
    	[ 2  P_t' ( ϑ^* - ϑ̃) +  P_t' ( ϑ̃ -  H ' ϑ̂ ) ] | 𝒟] 
    
    	
    	      =  P_t' ( ϑ̃ -  H ' ϑ̂ ) ^2_L_2
    	+ 2 𝔼[ . ( ϑ^* - ϑ̃)'  P_t  P_t' ( ϑ̃ -  H ' ϑ̂ ) | 𝒟] 
          = ϑ̃ -  H ' ϑ̂^2_2
    	+ 2 ( ϑ^* - ϑ̃)' ( ϑ̃ -  H ' ϑ̂ ) 
         ≤ϑ̃ -  H ' ϑ̂^2_2
    	+ 2 ϑ^* - ϑ̃_2 ϑ̃ -  H ' ϑ̂_2 ≤ 2 ϑ̃ -  H ' ϑ̂^2_2 +  ϑ^* - ϑ̃^2_2   .

The projection theorem implies

    Y_t -  P_t' ϑ̃^2_L_2 -  Y_t -  P_t' ϑ^* ^2_L_2 
    	=  P_t' ϑ̃ -  P_t' ϑ^*  ^2_L_2 
    	= ϑ̃ - ϑ^*  ^2_2, 
        Y_t -  P'_t ϑ^* ^2_L_2 -  Y_t -  X_t' θ^* ^2_L_2 =  u_t' γ^* ^2_L_2 .

The claim then follows from (<ref>), (<ref>), (<ref>), (<ref>) and (<ref>).




 §.§ Proof of Proposition <ref>




We begin by noting that

    P_t -  H  P_t 
     = Λ_K^-1/2 V_K'  X_t - Λ_K ^-1/2 V_K'  V_K Λ_K ^1/2Λ_K^-1/2 V_K'  X_t
     = Λ_K^-1/2 V_K' ( I_p -  V_K  V_K' ) X_t  
          =  Λ_K^-1/2 V_K'   V_R  V_R'  X_t 
     = Λ_K^-1Λ_K^-1/2 V_K'   V_KΛ_K  V_K'  V_R  V_R'  X_t  
          = Λ_K^-1Λ_K^-1/2 V_K' (  V_KΛ_K  V_K' +  V_RΛ_R  V_R')  V_R  V_R'  X_t  
          = Λ_K^-1Λ_K^-1/2 V_K' 1  T X'  X V_R  V_R'  X_t  
     =  Λ_K^-11√(T) P'   1 √(T) X    V_R  V_R'  X_t   .

This implies that for any ε>0

    ℙ ( 𝔼[ .  P_t -  H  P_t ^2_2| 𝒟] ≥ε )
     ≤ℙ ( 𝔼 [ . Λ_K^-1^2_2 1 √(T) P'  ^2_2 1  √(T) X  V_R  V_R'  X_t ^2_2| 𝒟 ] ≥ε ) 
          =   ℙ( Λ_K^-1_2^2 𝔼[ .  1 √(T) X    V_R  V_R'  X_t ^2_2| 𝒟] ≥ε) 
         ≤ℙ(  Λ_K^-1_2^2 ≥ε_1 ) +
     ℙ( 𝔼[ .  1 √(T) X    V_R  V_R'  X_t ^2_2| 𝒟] ≥ε_2 )  ,

for some ε_1,ε_2>0 such that ε = ε_1 ε_2.

We proceed by establishing bounds for the two terms in (<ref>).
First, we note that it follows from Proposition <ref> that for any η>0, for all T sufficiently large, it holds that

    ℙ( Λ_K^-1_2^2 ≥4   c_K^21
    p^2 α) = O(1 T^η)  .

Second, we establish a bound for the second term of equation (<ref>). We have that 

    ℙ( 𝔼[ .  1 √(T) X   V_R  V_R'  X_t ^2_2| 𝒟] ≥ε_2 ) 
    =  ℙ( 1  T  𝔼[ .∑_s=1^T  (  X_s'   V_R  V_R'  X_t  )^2 | 𝒟] ≥ε_2 ) 
          = ℙ ( 1  T  𝔼[ . ∑_s=1^T    (  X_s'   V_R  V_R'  X_t  X_t'  V_R  V_R'  X_s  ) | 𝒟] ≥ε_2 ) 
    = ℙ ( 1  T  ∑_s=1^T    X_s'   V_R Λ_R  V_R'  X_s ≥ε_2 )  
          = ℙ (  p  ( 1  T ∑_s=1^T   X_s'   V_R Λ_R  V_R'  X_s   p - (Λ_R^2)  p ) + (Λ_R^2)  ≥ε_2 ) 
         ≤ℙ ( p ( 1  T ∑_s=1^T   X_s'  V_R Λ_R  V_R'  X_s  p - (Λ_R^2)  p ) + c_K+1^2 p ≥ε_2 )

where we have used the fact that 𝔼(  X_s'  V_R Λ_R  V_R'  X_s) =  ( Λ_R^1/2 V_R' 𝔼( X_s  X_s')  V_R Λ_R^1/2 ) = (Λ_R^2) < c_K+1^2 p.

It is straightforward to verify that the sequence { X_s'  V_R Λ_R  V_R'  X_s / p - (Λ_R^2) / p} satisfies the conditions of Lemma <ref>, implying that 
for each η>0 there exists a constant C such that, for all T sufficiently large, it holds that 

    ℙ ( 𝔼[ .  1 √(T) X   V_R  V_R'
         X_t ^2_2| 𝒟] ≥ c_K+1^2 p + C p√(log(T)  T
        )) = O(1  T^η)  .

The claim of the proposition then follows from inequalities (<ref>) and (<ref>). 


 

Suppose <ref>–<ref> are satisfied. 

Then for any η>0, for any T sufficiently large, we have that 
ℙ( λ̂_K ≥ c_K  p^α / 2 ) ≥ 1 - T^-η. 



<ref> implies λ̂_K ≥λ_K  -|λ_K - λ̂_K| ≥ c_Kp^α - Σ  - Σ_2
where the last inequality follows from Weyl's inequality. 
To establish the claim, it suffices to show that for all T sufficiently large, 

    Σ  - Σ_2 ≤c_K  2 p^α

holds with probability at least 1 -T^-η.

Using the representation of Lemma <ref>  we get

    Σ  - Σ    =  1  T ∑_t=1^T (𝐁 P_t+ u_t )(𝐁 P_t+ u_t )'- 𝔼( X_t  X_t') 
        = 1  T 𝐁∑_t=1^T ( P_t  P_t'  -  I_K) 𝐁' 
    	+ 1  T∑_t=1^T( u_t  u_t' - 𝔼( u_t  u_t' )  ) 
    
    	    + 1  T ∑_t=1^T (𝐁 P_t  u_t') 
    	+ 1  T ∑_t=1^T (  u_t  P_t' 𝐁')  
    	= D_1 + D_2 + D_3 + D_4 .

This, in turn, implies that 

    ℙ( Σ  - Σ_2 > ε) 
    	≤∑_i=1^4 ℙ(  D_i _2 > ε_i )  ,

for some ε_1,ε_2,ε_3, ε_4>0 such that ε = ε_1 +ε_2+ ε_3 +ε_4.
Proposition <ref> and <ref> imply that for any η>0 there is a positive constant C_1 such that 

    D_1 _2 
    	    > 1  T ∑_t=1^T ( P_t  P_t'  -  I_K)   _2 𝐁𝐁' _2   
    	≥ p^α C_1  ( √( K   T ) + √(log T  T )) = ε_1
 
holds with probability at most T^-η.
Proposition <ref> implies that for any η>0 there is a positive constant C_2 such that 

    D_2 _2 >
    	C_2 [ ( p + log(T) )^r_α +1  r_α T +  √( ( p + log(T) )^r_α +1   r_α T )] = ε_2
 
holds with probability at most T^η.
Proposition <ref> and <ref> imply that for any η>0 there is a positive constant C_3 such that

    D_3 _2 
    	    > 1  T ∑_t=1^T  P_t  u_t' _2  𝐁_2 
    	≥ p^α/2 C_3 √( p K log T  T)  = ε_3
 
holds with probability at most T^-η.
Last, note that D_3 _2 =  D_4 _2 . 
Combining the inequalities in (<ref>), (<ref>), (<ref>) we get 

    ℙ ( Σ  - Σ_2 < ε) ≤ 1-4  T^η ,

where ε may be defined as 

    ε = p^α C_1  ( √( K   T ) + √(log T  T )) + p^α C_2 [ 1  p^α ( p + log(T) )^r_α +1  r_α T +  1  p^α√( ( p + log(T) )^r_α +1   r_α T )] 
          + 2 p^α C_3 √( p^1-α K log T  T).

The claim follows after noting that <ref> implies that, for all T sufficiently large, ε≤c_K 2 p^α.


 

Suppose <ref>–<ref> are satisfied. 
Then for any η>0 there exists a positive constant C such that, for any T sufficiently large,

    1  T ∑_t=1^T  u_t  u_t' - 𝔼(  u_t  u_t' ) _2≥ C [ ( p + log(T) )^r_α +1  r_α T +  √( ( p + log(T) )^r_α +1   r_α T )]

holds with probability at most T^-η.




We assume that c_K+1 is positive (when c_K+1 is zero the claim is trivial).
Consider the isotropic random vectors Σ_u^-1/2 u_t where Σ_u = 𝔼(  u_t  u_t' )  =  V_R  V_R' Σ V_R   V_R'
and note that <cit.> implies that if 𝒩 is a 1  4-net of 𝒮^p-1 then

    1  T ∑_t=1^T Σ_u^-1/2 u_t  u_t' Σ_u^-1/2 -  I_p _2
    	= max_ x ∈𝒮^p-1| 1 T∑_t=1^T ( u_t' Σ_u^-1/2 x)^2-1 | 
       ≤ 2 max_ x ∈𝒩| 1 T∑_t=1^T ( u_t' Σ_u^-1/2 x)^2-1 |
    	= 2 max_ x ∈𝒩| 1 T∑_t=1^T W_ x t| ,
 
where W_ x t = ( u_t'  Σ_u^-1/2 x)^2-1.
To establish the claim we first show that for all T sufficiently large (<ref>) can be bounded with high probability. 

We begin by establishing a bound for a fixed vector x ∈𝒩.

We enumerate three properties of the sequence { W_ x t}.
First, 𝔼(W_ x t)=0 since 𝔼[(  u_t'  Σ_u^-1/2 x)^2] =  x_2^2=1. 
Second, W_ x t is the de-meaned square of a sub-Gaussian random variable with parameter C_m (which is independent of x).

To see this note that u_t'  Σ_u^-1/2 x =  Z_t'  V_R Λ_R^1/2 V_R'  V_R Λ_R^-1/2 V_R '  x =  Z_t'   V_R   V_R'  x where Z_t = Σ^-1/2 X_t. 
Define ρ =  V_R  V_R'  x _2 and notice that ρ∈ [0,1].
If ρ∈ (0,1] then for any ε>0 it holds

    ℙ ( | u_t'  Σ_u^-1/2 x| ≥ε ) 
    = ℙ( | Z_t'  V_R  V_R'  x ρ| ≥ερ) 
    ≤exp (-C_m (ε /ρ )^2 ) 
    ≤exp (-C_m  ε  ^2 )
 
where C_m>0 is defined in <ref>. 
If ρ = 0 then for any ε>0 it holds ℙ ( | u_t'  Σ_u^-1/2 x| ≥ε ) = 0 ≤exp (-C_m  ε  ^2 ).
Therefore u_t'  Σ_u^-1/2 x is sub-Gaussian with parameter C_m.

Third, the sequence {W_ x t}_t=1^T inherits the mixing properties of the sequence 
{(Y_t, X_t')'}_t=1^T spelled out in <ref>.

These three facts imply that { W_ x t} satisfies the conditions of <cit.> (the C_r inequality and <cit.> imply that the condition spelled out in equation (1.33) of <cit.> is satisfied).
Define
ε_T =  C_1^*( p + log(T) )^r_α +1  r_α T +  [  C_1^* ( p + log(T) )^r_α +1   r_α T ]^1/2 and 
q_T =  ⌈ T  C^*_2 (p + log(T) )^1  r_α⌉ - 1 for
positive constants C_1^* and C_2^* to be chosen below.
Notice that <ref> implies that for all T sufficiently large it holds that q_T ∈ [1,T  2], as required by the theorem.
Then for any r≥ 3 there exist a positive constant C_1 that depends on C_m and r such that, for all T sufficiently large,

    ℙ( | 1  T∑_t=1^T W_ x t| > ε_T ) 
    	≤ a_1 Texp(-q_T ε_T^2 C_1 + C_1 ε_T) + a_2 Tα( ⌊ T  q_T +1 ⌋)^2r  2r+1
 
holds, where
a_1 T = 2 T / q_T + 2 [ 1 + ε_T^2 / (C_1 + C_1 ε_T) ], 
and 
a_2 T = 11 T( 1 + C_1 / ε_T ).
We proceed by bounding the r.h.s. of (<ref>).
First, for all T sufficiently large, we have

    a_1 Texp(-q_T ε_T^2 C_1 + C_1 ε_T) ≤( 2 T + 2 + 2 ε_T  C_1 ) exp(-min( ε_T, ε_T^2 )    2 C_1  q_T ) 
         ≤exp( log( 3 T + 2 ε_T  C_1 ) - C_1^*(p + log(T) )^r_α +1  r_α 2 T C_1 (  T  C^*_2 (p + log(T) )^1  r_α -1 )) 
         ≤exp( - (  C_1^*   2 C_1 C_2^* - 1 ) (p + log T))  ,

where in the second inequality we use the fact that min(ε_T,ε_T^2) ≥ C_1^* (p + log(T) )^r_α +1  r_α / T 
and the last from the condition r_p < r_α.
Second, for all T sufficiently large, we have

    a_2 Tα( ⌊ T  q_T +1 ⌋)^2r  2r+1≤exp( 2 log(T ) - C_α2 r  2r+1( T  q_T +1  - 1)^r_α) 
         ≤exp( 2 log(T ) - 1 2 C_α  (C^*_2)^r_α2r  2r+1( p + log(T) ) ) 
         ≤exp(  - ( C_α (C^*_2)^r_αr  2r+1-1 ) ( p + log(T) ) )  .

Combining (<ref>) and (<ref>) we get that for a given x, for all T sufficiently large, it holds

    ℙ( | 1  T∑_t=1^T W_ x t| > ε_T ) 
    	≤exp( - (  C_1^*   2 C_1 C_2^*  -1) (p + log T)) 
          +  exp(  - ( C_α  (C^*_2)^r_αr  2r+1-1 ) ( p + log(T) ) )  .
 
The next step consist in taking the union bound over all the vectors x ∈𝒩. 
It follows from <cit.> that the cardinality of a 1  4-net 𝒩 of the unit sphere 𝒮^p-1 is bounded by 9^p. 
Setting  C_2^* = ((η + log(9) + 1) (2r+1)  r C_α)^1  r_α and C_1^* = 2 C_1 C_2^* (η + log(9) + 1) in (<ref>) we then obtain that, for all T sufficiently large,

    ℙ   ( max_ x ∈𝒩| 1 T∑_t=1^T W_ x t| > ε_T ) 
    	≤ 9^p max_ x ∈𝒩ℙ( | 1 T∑_t=1^T W_ x t| > ε_T ) 
         ≤ 2 exp( log(9) p - (η + log(9))( p + log(T) ) ) < 2 exp(-ηlog(T)) = 2  T^η .

The claim follows after noting that, for all T sufficiently large, it holds

    ℙ( 1  T ∑_t=1^T  u_t  u_t' - 𝔼(  u_t  u_t' ) _2  > 2 Σ_u_2 ε_T  ) 
     = ℙ( 1  T ∑_t=1^T Σ_u^-1/2 u_t  u_t' Σ_u^-1/2  -  I_p _2 > 2 ε_T )  
         ≤ℙ( max_ x ∈𝒩| 1 T∑_t=1^T W_ x t|  > ε_T ) = O(1  T^η) ,

and noting that <ref> implies that Σ_u_2 = c_K+1. 


Let λ_min( M) denote the smallest eigenvalue of the square matrix M.


Suppose <ref>, <ref> and <ref>  are satisfied. 
Then for any η>0 there exists a positive constant C such that, for any T sufficiently large,

    (i) ℙ( 1  T ∑_t=1^T  P_t  P_t' - 𝔼(  P_t  P_t' ) _2≥ C  ( √( K   T ) + √(log T  T )) ) = 1  T^η , 
        (ii) ℙ( λ_min( 1  T ∑_t=1^T  P_t  P_t'
        ) ≤1 2) = 1  T^η , 
        (iii) ℙ( ( 1  T ∑_t=1^T  P_t 
        P_t')^-1 - ( 𝔼(  P_t  P_t' ) )^-1_2≥ C  ( √(
        K   T ) + √(log T  T )) ) = 1  T^η .




(i) Following the same arguments of Proposition <ref> and denoting by 𝒩 the 1  4-net of the unit sphere 𝒮^K-1 we get that

    1  T ∑_t=1^T  P_t  P_t' - 𝔼(  P_t  P_t' ) _2≤ 2 max_ x ∈𝒩| 1 T∑_t=1^T ( P_t'  x)^2-1  |
    = 2 max_ x ∈𝒩| 1 T∑_t=1^T W_ x t|  ,
 
where W_ x t = ( P_t'  x)^2-1.
To establish the claim, we first show that for all T sufficiently large (<ref>) can be bounded with high probability. 
We note two properties of the sequence { W_ x t}.
First, 𝔼(W_ x t)=0 since 𝔼[( P_t'  x)^2] =  x_2^2=1. 

Second, W_ x t is sub-exponential with parameter C'_m (which is independent of x and depending on C_m).
To see this note that |  P_t'  x | = |  Z_t'  V Λ^1/2 V'  V_K Λ_K^-1/2 x | = |  Z_t'  V_K  x| where Z_t = Σ^-1/2 X_t and that V_K  x _2 ∈ [0,1].

Consider the decomposition ∑_t=1^T W_ x t = ∑_t=1^T W'_ x t + ∑_t=1^T W”_ x t where W'_ x t =  W_ x t1(|W_ x t| ≤ b_T) - 𝔼( W_ x t1(|W_ x t| ≤ b_T ) ) and 
W”_ x t  =  W_ x t1(|W_ x t| > b_T) - 𝔼( W_ x t1(|W_ x t| > b_T) ).
Then for any ε>0 we have that

    ℙ( | ∑_t=1^T W_ x t| > ε) 
    	   ≤ℙ( |∑_t=1^T W'_ x t| >  ε 2)   
     + ℙ( | ∑_t=1^T  W”_ x t| >ε 2)  .

The sequence { W'_ x t}_t=1^T is such that W_ x t' _∞ < 2b_T and has the same mixing properties as {(Y_t, X_t)}_t=1^T spelled out in <ref>.
These two facts imply that { W'_ x t} satisfies the conditions of <cit.>.
Define
ε_T = C^* ( √( K T )   + √( T log T) ),
b_T = 2  C_m' [ log ( 2  W_ x t_L_2√(T) / C^* ) + C^*(K+log T ) ] and 
M_T = ⌊ b_T^-1 T^1 2 / ( √( K  )   + √(log T)  )⌋ for positive constant C^* to be chosen below.
For all T sufficiently large, we have that M_T ∈ [1,T] (note <ref> implies r_k < 1/3) and 4 (2 b_T) M_T < ε_T, as required by the theorem. 
Then, for all T sufficiently large, 

    ℙ( | ∑_t=1^T W'_ x t| > ε_T ) 
    	< 4 exp( - ε_T^2  64 T  M_T  D(T,M_T) + 16  3 b_T M_T ε_T ) + 4 T M_Texp( -C_α M_T^r_α)

holds with D(T,M_T) =  𝔼[ ( ∑_t=1^M_T  W'_ x t)^2 ].
Define γ(l) = |Cov(W'_ x t, W'_ x t+l)| for l=0,…,T-1
and note that D(T,M_T) ≤ M_T ∑_l=-T+1^T-1γ(l). 
Define C_m 4 =  W_ x t^2_L_4 (which is a constant depending only on C_m).
Then, for l=0,… it holds that

    γ(l) 
    	≤ 12 α(l)^1  2 W'_ x t^2_L_4≤ 48 α(l)^1  2 W_ x t^2_L_4≤ 48 α(l)^1  2 C_m,4 ,
 
where the first inequality follows from Davydov's inequality <cit.>
and the second follows from the fact that W_ x t' _L_4≤ 2  W_ x t1(|W_ x t| ≤ b_T) _L_4≤ 2  W_t_L_4.

This implies that D(T,M_T) < C_σ^2 M_T where C_σ^2 = 96C_m,4∑_l = 0^∞α(l)^1  2∨ 1.
We then use the inequality a^2 + b^2 ≤ (a+b)^2 for a,b>0 to get that

    ℙ( | ∑_t=1^T W'_ x t| > ε_T ) 
    	≤ 4 exp( -  C^*2 (√(KT)+√(T log(T))  )^2  64 T C_σ^2 + 16  3 b_T M_T ε_T ) + 4 T  M_Texp( - C_α M_T^r_α) 
         ≤ 4 exp( -  C^*2 K T   + C^*2 T log(T) 64 T C_σ^2 + 16  3 C^*T  ) + 4   T exp( - C_α M_T^r_α) 
         ≤ 4 exp( -  C^*2 64 C_σ^2 + 16  3 C^*( K + log(T)  ) ) + 4  exp(log(T)- C_α M_T^r_α)   .

Note that for all T sufficiently large, we have M_T^r_α > K + log(T) since r_K < 1 3 + 2  r_α as implied by <ref>.


We may write that 

    ℙ( | ∑_t=1^T W'_ x t| > ε_T ) 
    	   ≤ 5 exp( -  C^*2 64 C_σ^2 + 16  3 C^*( K + log(T)  ) )    .

The sequence { W_ x t”}_t=1^T is such that, for all T large enough, 

    ℙ( | ∑_t=1^T W”_ x t| > ε_T) 
    	≤1 ε_T𝔼| ∑_t=1^T W”_ x t|  
    	≤T ε_T𝔼 | W”_ x t | ≤2 T ε_T𝔼| W_ x t1(|W_ x t| > b_T) | 
         ≤2T ε_T W_ x t_L_2 1( |W_ x t| > b_T  ) _L_2 
    	= 2T ε_T W_ x t_L_2ℙ( |W_ x t| > b_T  )^1 2≤2 T  W_ x t_L_2ε_Texp( -  C_m' b_T  2 ) 
          = 2 T  W_ x t_L_2 C^* (√(K T )  + √( T log(T) )) exp( - C_m' b_T  2 ) ≤2  W_ x t_L_2√(T)  C^*exp( - C_m' b_T  2 ) 
          = exp( log(2  W_ x t_L_2√(T)  C^*) -  C_m' b_T  2 )
    	= exp( -C^* ( K + log(T) ))   ,

where the first inequality follows from Markov's inequality.

Combining (<ref>) and (<ref>) we have that, for all T sufficiently large,

    max_x ∈𝒩ℙ( | 1  T∑_t=1^T W_ x t| > ε_T  T ) ≤exp( -C^* (K + log (T)) ) 
    	+ 5 exp( -  C^*2 64 C_σ^2 + 16  3 C^*( K + log(T)  ) )   ,
 
for the fixed vector x. 

It remains to take the union bound over all the vectors x ∈𝒩. 
Using the same arguments of Proposition <ref> we have that, for all T sufficiently large,

    ℙ(  max_x ∈𝒩| 1 T∑_t = 1^T W_ x  t|
    > ε_T  T ) 
    ≤ 9^K max_x ∈𝒩ℙ( | 1 T∑_t = 1^T W_ x t| > ε_T  T) 
         ≤ 9^K  exp( -C^* (K + log(T)) ) + 9^K · 5 exp( -  C^*2 64 C_σ^2 + 64  3 C^*( K + log(T)  ) ) ≤1  T^η

where the last inequality follows for a sufficiently large choice of the constant C^*.
The claim follows after noting that, for all T sufficiently large, it holds

    ℙ( 1  T ∑_t=1^T  P_t  P_t' - 𝔼(  P_t  P_t' ) _2  > 2 ( √( K  T ) + √(log(T) T))  ) 
    ≤ℙ( max_ x ∈𝒩| 1  T∑_t=1^T W_ x t|  > ε_T  T ) ≤1  T^η .

(ii) We begin by noting that 

    λ_min(1  T ∑_t=1^T  P_t  P_t') = min_ x ∈𝒮^K-1 x' ( 1  T ∑_t=1^T  P_t  P_t' )  x 
          = min_ x ∈𝒮^K-1 x'  I_K  x -  x'  ( I_K- 1  T ∑_t=1^T  P_t  P_t' )  x  
    ≥ 1 - 1  T ∑_t=1^T  P_t  P_t' -  I_K _2  .

It then follows from part (i) that for any η>0, for all T sufficiently large, 1 - 1  T ∑_t=1^T  P_t  P_t' -  I_K _2 ≥1 2
holds with at least probability 1-T^-η, which implies the claim.

(iii) First, we condition on the event of part (ii), which implies that for any η>0, for all sufficiently large T, ( 1  T ∑_t=1^T  P_t  P_t')^-1 exists.
Then we note that conditional on the same event for any η>0 there exists a positive constant C such that, for all sufficiently large T, it holds that 

    ℙ ( ( 1  T ∑_t=1^T  P_t  P_t')^-1 - 𝔼(  P_t  P_t' )^-1_2≥C 2 ( √( K   T ) + √(log(T)  T ))  ) 
          = ℙ ( ( 1  T ∑_t=1^T  P_t  P_t')^-1(  I_K - 1  T ∑_t=1^T  P_t  P_t')_2≥C 2 ( √( K   T ) + √(log(T)  T ))   )  
         ≤ℙ ( ( 1  T ∑_t=1^T  P_t  P_t')^-1_2  ≥1  2) 
    	+ ℙ( 1  T ∑_t=1^T  P_t  P_t' - 𝔼(  P_t  P_t' )  _2≥ C  ( √( K   T ) + √(log(T)  T ))   ) 
          = 2 T^η ,

where we have used the fact that 𝔼(  P_t  P_t' )^-1 =  I_K.
The unconditional probability of this event being realized is ( 2T^-η ) (1 - T^-η ) = T^-η.




Suppose <ref>, <ref>, <ref> and <ref> are satisfied. 

Then for any η>0 there exits a positive constant C such that, for any T sufficiently large, it holds that 

    ℙ( 1  T∑_t=1^T  P_t u_t' _2 ≥ C √(
    p K log(T)  T)) = 1  T^η .





We assume that c_K+1 is positive (when c_K+1 is zero the claim is trivial).
Let V_ij,t denote P_itu_jt and V_j,t denote the j-th column of P_t u_t' where 1≤ i≤ K and 1 ≤ j ≤ p.  



We begin by showing that, for each j, the sequence of  K-dimensional random vectors { V_j,t}_t=1^T satisfies the conditions required in Lemma <ref>.

Lemma <ref>.(ii) and (iii) establish that P_t  and u_t are sub-Gaussian random vectors.
Standard results on sub-Gaussian random variables imply that  

    ℙ( sup_ v :  v _2 = 1  | V_j t '  v | > ε) ≤ℙ( sup_ v :  v _2 = 1  | P_t '  v | | u_jt | > ε) ≤exp(-C_m' ε)

for some C_m' > 0.
Lemma <ref> implies that 𝔼(  V_j,t) =  𝔼( P_tu_jt) =  0, hence V_j,t is a zero-mean random vector.
Moreover, standard properties of strong mixing processes imply that { V_j,t}_t=1^T inherits the mixing properties of the sequence {(Y_t, X_t)'}_t=1^T spelled out in <ref>.
Lastly, <ref> implies that K = ⌊ C_K T^r_K⌋ where r_K<1.

Then the conditions of Lemma <ref> applied to the sequence { V_j,t}_t=1^T are satisfied and picking η' = η+r_p  we get that there exists a C such that, for all T sufficiently large,

    ℙ( 1  T∑_t=1^T  P_t u_t' _2  ≥ C √( p K log(T)  T)) 
    	 ≤ℙ( √(p)max_1≤ j ≤ p1  T∑_t=1^T  V_j,t_2 ≥ C √( p K log(T)  T))
         ≤ p max_1≤ j ≤ pℙ(  1  T∑_t=1^T  Z_j,t_2 ≥ C √( K log(T)  T)) 
    	= p  T^η' = C  T^r_p T^η+r_p = C  T^η .





 §.§ Proof of Proposition <ref>




Recall that ϑ̃ = ( 1  T P'  P )^-11  T P '  Y and ϑ̂ = 1 T P'  Y and note that

    ϑ̃ -  H ' ϑ̂ 
    	=   ϑ̃ -  H ^-1 H  H'ϑ̂  
    	= ( 1  T P'  P )^-11  T P '  Y -  H ^-1 H  H' 1 T P'  Y 
          = [  ( 1  T P'  P )^-11  T P '  Y - 1  T P '  Y  ] -   H ^-1(   H  H' 1 T P'  Y - 1  T P'  Y + 1  T P'  Y - 1  T H  P'  Y )  
          = [ ( 1  T P'  P )^-1 -  I_K ] 1  T P ' Y  -   H ^-1[ (  H  H' -  I_K   ) √(1  T) P' +  √(1  T) (   P' -  H  P' ) ] √(1  T) Y   .

Then the triangle inequality and the implication rule imply that 
for any ε>0 and ε_i>0 for i=1,…,5 such that ε = ε_1ε_2 + ε_3 ε_5 + ε_4 ε_5 it holds that

    ℙ( ϑ̃ -  H ' ϑ̂_2 > ε ) 
    ≤ℙ( ( 1  T P'  P )^-1 -  I_K  _2  > ε_1 ) + 
    ℙ( 1 √(T) P' _2   1 √(T) Y_2  > ε_2 ) 
          + ℙ(  H  H' -  I_K  _2  > ε_3 ) 
    + ℙ(  1 √(T) P' -  H  P'  _2 > ε_4 ) 
    + ℙ(  H^-1_2  1 √(T) Y_2 > ε_5 )  .

The claim then follows from Proposition <ref>, Proposition <ref>, Proposition <ref> and Proposition <ref> by setting
ε_1 = C_1 ( √( K  / T ) + √(log(T) /T ) ),
ε_2 = √( 6 log (T) / C_m ),
ε_3 = C_2 [ √( K / T ) + √(log(T) / T ) +  (p + log(T))^r_α +1  r_α / (p^α T)  + 1 /p^α ],
ε_4 =  C_3 [  (p + log(T))^ r_α + 1  r_α / (p^αT) +1 / p^α ] and
ε_5 = √( 3 log (T) / (2 C_m) ).
The same propositions imply that the r.h.s. of (<ref>) can be bounded by O(T^-η).




Suppose <ref>–<ref> are satisfied. 

Then for all η>0 there exists a C > 0 such that, for any T sufficiently large,

    √(1  T) P -  P   H' _2
    ≤ C [  ( p + log(T) ) ^ r_α + 1  r_α p^αT  +  1  p^α]

holds with probability at least 1-T^-η.	




Let P =  X  V_K Λ_K^-1/2 and P =  X  V_K  Λ_K^-1/2 where X = (  X_1 , … ,  X_T )'.
We note that

    P -  P   H'   =  X  V_K Λ_K^-1/2  
     -   X  V_K Λ_K ^1/2Λ_K^-1/2 V_K'  V_K Λ_K ^-1/2 =   X  ( I_p -  V_K  V_K' )  V_K Λ_K^-1/2
          =   X   V_R  V_R'   V_K Λ_K^-1/2 
     =  X   V_R  V_R'  V_KΛ_K  V_K'  V_K Λ_K^-1/2Λ_K^-1
          =   X   V_R  V_R' (  V_KΛ_K  V_K' +  V_RΛ_R  V_R')   V_K Λ_K^-1/2Λ_K^-1 = 1 T X   V_R  V_R'  X'  X  V_K Λ_K^-1/2Λ_K^-1
          = 1 √(T) X   V_R  V_R'  X'  1 √(T) PΛ_K^-1 
     = 1√(T)∑_t=1^T  u_t  u_t'   1 √(T) PΛ_K^-1 .

This implies that for any ε,ε_1,ε_2>0 such that ε = ε_1 ε_2 it holds

    ℙ (  √(1  T) P -  P   H' _2  > ε ) 
     ≤ℙ (  1  T ∑_t=1^T  u_t  u_t'  _2   1 √(T) P_2 Λ_K^-1_2   > ε ) 
          = ℙ(  1  T ∑_t=1^T  u_t  u_t'   _2  Λ_K^-1_2    > ε)   
     ≤ℙ(  Λ_K^-1_2  >ε_1 ) +
     ℙ(  1 T∑_t=1^T  u_t  u_t'  _2  > ε_2 )  .

We proceed by bounding the two terms on the r.h.s. of the last inequality.
First we note that Proposition <ref> implies that, for all T sufficiently large

    ℙ( Λ_K^-1_2 > 2   c_K p^α)
     = 1- ℙ( 1 λ_K≤2   c_K p^α)  
     = O(1  T^η)  .

Second, we note that 

    1 T∑_t=1^T  u_t  u_t'  _2
    ≤1  T∑_t=1^T  u_t  u_t' - 𝔼( u_t  u_t') _2 + 𝔼( u_t  u_t') _2 
    = 1  T∑_t=1^T  u_t  u_t' - 𝔼(  u_t  u_t' )  _2  + c_K+1 .


Proposition <ref> then implies that, for all T sufficiently large, we have

    ℙ(  1  T ∑_t=1^T  u_t  u_t' _2  > C (  (p+log(T))^r_α + 1  r_α T   + √((p+log(T))^r_α +1  r_α T)) + c_K+1)
    =  O(1  T^η) .
 
The claim of the proposition then follows from inequalities (<ref>) 
and (<ref>) after noting that  

    C (  (p+log(T))^r_α + 1  r_α T   + √((p+log(T))^r_α +1  r_α T)) + c_K+1≤ C' (  (p+log(T))^r_α + 1  r_α T   + c_K+1)  .





Suppose <ref>–<ref> are satisfied. 

Then for any η>0 there exist a positive constant C such that, for any T sufficiently large, 

    H  H'-  I_K _2≤ C  ( √( K   T ) + √(log(T) T ) 
    	+  (p+log(T))^r_α +1  r_α p^α T + 1  p^α) ,

holds with probability at least 1- T^-η.



By repeated application of the triangle inequality we get

    H  H'-  I_K _2≤ H  H' - 1  T H  P'  P  H'  _2 +  1  T H  P'  P  H'  -  I_K _2
         ≤ H _2^2   I_K - 1  T P'   P _2  +  1  T H  P'  P  H'  - 1  T P'  P  H'  + 1  T P'  P  H'- 1  T P'  P_2
         ≤ H _2^2  1  T∑_t=1^T  P_t  P_t'  -  I_K _2  +  1  T (  P  H'-  P )'  P  H'  _2  +  1  T P' (  P  H'-  P )  _2
         ≤ H _2^2  1  T∑_t=1^T  P_t  P_t' - I_K _2  +  1 √(T) P -  P  H' _2  ( 1 √(T) P _2  H _2  + 1 √(T) P_2  )   .

For any ε>0, ε_1>0, ε_2>0, ε_3>0 and ε_4>0 such that ε = ε_1ε_2 + ε_3 ε_4 it holds that

    ℙ (  H  H'-  I_K _2≥ε )  
    	≤ℙ(  H _2^2  ≥ε_1 ) + 
    	ℙ(    1  T∑_t=1^T  P_t  P_t' -  I_K _2≥ε_2 ) 
          + ℙ( √(1  T) P -  P   H'  _2  ≥ε_3 )  
    	+ ℙ( 1 √(T) P _2   H _2  + 1 √(T) P_2 > ε_4 )  .

The claim then follows from Proposition <ref>, Propositions <ref> and Proposition <ref> by setting
ε_1 = 2 c_1/c_K, ε_2 = C_1 ( √( K  / T ) + √(log T /T ) ),
ε_3 =  C_2 [  (p + log(T)) ^ r_α + 1  r_α / (p^αT) +1/p^α]
and ε_4 = 2 √(c_1/c_K) + 1. The same propositions imply that the r.h.s. of (<ref>) can be bounded by O(T^-η).




Suppose <ref>–<ref> are satisfied. 
Then for any η>0, for any T sufficiently large, it holds that
(i) ℙ ( √(1 / T) P _2  ≥√(2) ) = O( T^-η ),
(ii) ℙ (  H _2≥√(2c_1 /  c_K) ) = O( T^-η ),
(iii) ℙ (  H^-1_2≥2 √(c_1 /  c_K) ) = O( T^-η ),
(iv) ℙ ( √( 1 / T) Y  _2 > √(ηlog(T)/C_m ) ) =  O( T^-η ).



(i) By the triangle inequality, the fact that 𝔼(  P_t  P_t' ) =  I_K and Proposition <ref>
we have that for any η>0 there exists a positive constant C such that, for all T sufficiently large, 

    √(1  T) P ^2_2  
    	≤1 T P'  P -  I_K  _2 +  I_K _2
    	≤ 
    	C  ( √( K  T ) + √(log T  T ))  + 1 
    	≤ 2

 holds with probability at least 1-O(T^-η).

(ii) We begin by noting that 

    H_2 
    = Λ_K ^-1/2 V_K'  V_K Λ_K ^1/2_2≤Λ_K ^-1/2_2 V_K _2  V_K  _2Λ_K ^1/2_2 
    =  √(c_1 p^α)Λ_K ^-1/2_2  ,
 where we have used the fact that <ref> implies Λ_K ^1/2_2 = √(c_1 p^α).
Now we may write 

    ℙ(  H _2≥√(2c_1  c_K)) 
    	≤ℙ( √(c_1 p^α)Λ_K ^-1/2_2    ≥√(2c_1 c_K)) 
    	= ℙ( c_1 p^α1 λ_K≥ 2 c_1  c_K) 
          = 1- ℙ( λ_K ≥ c_K p^α 2)
    	≤ O(1  T^η) ,

where the last inequality is implied by Proposition <ref>.

(iii) We begin by noting that

    H^-1_2 
        =  H' ( H')^-1  H^-1_2 ≤ H _2   ( H')^-1 H^-1_2 
        =  H _2  I_K + ( H')^-1 H^-1  -  I_K _2  
       ≤ H _2  +  H _2  ( H')^-1 H^-1 -  I_K  _2  
        ≤ H _2  +  H _2  H  H' -  I_K _2 
         1- H  H' -  I_K_2   ,

where we have used the inequality 

    A^-1 -  B^-1_2 ≤ A^-1_2^2  B -  A _2  1 -  A^-1_2  B -  A _2  ,

where A and B are invertible n× n matrices.
The claim then follows from Proposition <ref> and part (ii) of this proposition.

(iv) By <ref>, for any ε > 0,
ℙ( √( 1 / T) Y _2 > ε)   
≤ℙ( max_t ≤ T |Y_t| > ε) 
≤ T ℙ(|Y_t| > ε) 
≤ T exp ( -C_m  ε^2 ).
Thus, by choosing ε = √(ηlog(T)/C_m ) we have that √( 1 / T) Y  _2  > √( (1+η)log(T)/C_m ) holds at most with probability O(T^-η).




 §.§ Proof of Proposition <ref>




Define the empirical risk differential for an arbitrary ϑ∈ℝ^K as

    ℒ_ϑ = R_T(ϑ) - R_T(ϑ^*) 
    	= 1  T∑_t=1^T (  P_t' ϑ -  P_t' ϑ^* )^2 + 2  T∑_t=1^T (Y_t- P_t' ϑ^*  )( P_t' ϑ -  P_t' ϑ^* )  .
	
Assume that it holds that 

    P_t ' ϑ -   P_t ' ϑ^* _L_2 = ϑ -   ϑ^* _2  >  72 C^1 2_σ^2κ_1^2 κ_2 √(K log (T)  T) .

Condition on the events of Proposition <ref> and Proposition <ref>,
for any η>0, for any T sufficiently large, with probability at least 1-O(T^-η), we have that

    1  T∑_t=1^T (  P_t ' ϑ -   P_t ' ϑ^* )^2 
    	   (a)≥κ_1^2 κ_2  2 P_t ' ϑ -   P_t ' ϑ^* ^2_L_2(b)> 36 C^1 2_σ^2 P_t ' ϑ -   P_t ' ϑ^*  _L_2 √(K log (T)  T)
       (c)≥| 2  T∑_t=1^T (Y_t- P_t ' ϑ^*   )(  P_t ' ϑ -   P_t ' ϑ^*  ) |  ,
	
where 
(a) follows from Proposition <ref>,
(b) follows from condition (<ref>),
and (c) follows from Proposition <ref>.
Thus, conditional on the events of Proposition <ref> and Proposition <ref> and assuming (<ref>) holds we have high probability that ℒ_ϑ > 0.
Since the empirical risk minimizer ϑ̂ satisfies ℒ_ϑ̂≤ 0 then conditional on the same events we have P_t ' ϑ̂ -   P_t ' ϑ^* _L_2≤ 72 C^1 2_σ^2κ_1^2 κ_2 √(K log (T)  T). 
The claim then follows after noting that 

    Y_t -  P_t' ϑ̃^2_L_2 -  Y_t -  P_t' ϑ^* ^2_L_2
    
    	=  P_t' ϑ̃ -  P_t' ϑ^*  ^2_L_2≤ C_σ^2( 72 κ_1^4 κ_2^2 )^2  K log (T)  T .

It is important to emphasize that the L_2 norm in (<ref>) is the L_2 norm conditional on {ϑ̃ = ϑ̃(𝒟)}. 
The equality in (<ref>) follows from the fact that 𝔼 [( Y_t-  P_t ' ϑ^* )( P_t' ϑ^*-f̃^PCR_ϑ t )] =  𝔼 [( Y_t- P_t' ϑ^* )  P_t' (ϑ^* -ϑ )] = 0, which is implied by the first order condition for a minimum for R(ϑ), as ϑ^* is the unique value of ϑ such that  
𝔼 [( Y_t-  P_t ' ϑ )  P_t']  = 0. 




Suppose <ref>–<ref> are satisfied.

Then for any η>0, for all T sufficiently large and any ϑ∈ℝ^K,

    1  T∑_t=1^T (  P_t ' ϑ^* -  P_t ' ϑ )^2 
    ≥κ_1^2 κ_2  2 P_t ' ϑ^* -  P_t ' ϑ^2_L_2 ,

holds with probability at least 1-T^-η.





This follows from <cit.>. 
Note that the proposition there establishes an analogous claim for η=1,
but inspection of the proof shows that it is straightforward to allow for any η>0.
Note that those results require that r_K < r_α / (r_α + 1), 
which is implied by <ref>.
Also, note that <ref> implies that the small-ball condition is also satisfied by 
P_t ' ϑ^* -  P_t ' ϑ.




Suppose <ref>–<ref> are satisfied.


Then for any η>0 and any ϑ∈ℝ^K,
there exists a positive constant C such that, for all T sufficiently large

    | 1  T∑^T_t=1(Y_t- P_t ' ϑ^*)( P_t ' ϑ^*-  P_t ' ϑ ) | ≤ C  P_t ' ϑ^* -  P_t ' ϑ_L_2 √(K log (T)  T) ,

holds with probability at least 1-T^-η.




We begin by noting that for any ϑ∈ℝ^K ∖ϑ^* we have that

    | ∑^T_t=1(Y_t- P_t ' ϑ^*)( P_t ' ϑ^*- P_t ' ϑ) / T  P_t ' ϑ^* -  P_t ' ϑ_L_2| 
    	= | 1  T∑^T_t=1 (Y_t- P_t ' ϑ^*)  P_t' ν| 
          = | 1  T∑^T_t=1 [ (Y_t- P_t ' ϑ^*)  P_t' ] ν| = | 1 T∑^T_t=1 W_t'ν|  ,

where W_t=(W_1 t,…,W_K t)' with W_i t = (Y_t- P_t ' ϑ^*) P_it and ν =  (ϑ^*-ϑ) / P_t ' ϑ^* - P_t ' ϑ_L_2. 
Note that ν_2 = 1. Then, for any ϑ∈ℝ^K ∖ϑ^* it holds

    ℙ( | ∑^T_t=1(Y_t- P_t ' ϑ^*)( P_t ' ϑ^*- P_t ' ϑ)|  T  P_t ' ϑ^*- P_t ' ϑ_L_2 > ε) ≤ℙ( sup_ϑ∈ℝ^K ∖ϑ^* | ∑^T_t=1(Y_t- P_t ' ϑ^*)( P_t ' ϑ^*- P_t ' ϑ ) | T  P_t ' ϑ^*- P_t ' ϑ_L_2 > ε) 
          = ℙ( sup_ν: ν_2 =1|  1 /T∑^T_t=1 W'_tν| >ε) 
    	≤ℙ(  1/T∑^T_t=1 W_t _2 >   ε)  .

<ref> and Lemma <ref> imply that W_t is sub-exponential for some parameter C_m'>0 for each i.
Standard properties of strong mixing processes imply that { W_t} inherits the mixing properties of { (Y_t, X_t')' } spelled in <ref>.
Assuming that <ref> is satisfied we have that Lemma <ref> holds which implies that, for any η>0 there exists a positive constant C such that, for all T sufficiently large,

    sup_ϑ∈ℝ^K ∖ϑ^* | ∑^T_t=1(Y_t- P_t ' ϑ^*)( P_t ' ϑ- P_t ' ϑ^* ) |  T  P_t ' ϑ -  P_t ' ϑ^*_L_2≤ C √(K log (T)  T)

holds with probability at least 1-O(T^-η). This implies the claim.




 §.§ Proof of Proposition <ref>




The claim follows from the fact that u_t' γ^* ^2_L_2 = (γ^*)'  V_R Λ_R  V_R' γ^* = (θ^*)'  V_R Λ_R  V_R' θ^*
from Lemma <ref>.




§ AUXILIARY RESULTS









= 1 
 
Suppose <ref> and <ref> are satisfied.

Then we have that (i) there exists some constant C_1>0 such that P_t is a sub-Gaussian vector with parameter C_1; 
(ii) if c_K+1>0 then there exists some constant C_2>0 such that u_t is sub-Gaussian vector with parameter C_2 otherwise u_t is degenerate at zero. 



(i) Since P_t = Λ_K^-1/2 V_K'  X_t =  V_K'  Z_t, we have that for any ε>0

    ℙ( sup_ v:  v _2 = 1 | v' P_t| > ε) 
    	≤ℙ( sup_ v:  v _2 = 1 | v' Z_t| > ε) 
    	≤exp(-C_m ε ^2)  .

Then, we have that P_t is a sub-Gaussian vector with parameter C_1=C_m.

(ii) We assume that c_K+1>0.
Since u_t =  V_R  V_R'  X_t =  V_R Λ_R^1/2 V_R'  Z_t, we have that for any ε>0

    ℙ( sup_ v:  v _2 = 1 | v' u_t| > ε) 
    	≤ℙ( sup_ v:  v _2 = 1 c_K+1^1/2 | v' Z_t| > ε) 
    	≤exp(-C_m  c_K+1ε ^2)  ,

where we have used the fact that V_R Λ_R^1/2 V_R'_2 
≤ V_R _2  Λ_R^1/2_2  V_R'_2 
= c_K+1^1/2 . 
Then we have that that u_t is a sub-Gaussian vector with parameter C_2=C_m/c_K+1.




Let { Z_t }_t=1^T be a stationary sequence of d-dimensional zero-mean random vectors.
Suppose
(i) for any ε>0 it holds sup_1≤ i≤ dℙ( |Z_i t | > ε ) ≤exp( -C_m ε ) for some C_m>0; 

(ii) the α-mixing coefficients of the sequence satisfy α(l) < exp( -C_α l^r_α ) for some C_α>0 and r_α > 0; and
(iii) d = ⌊ C_d T^r_d⌋ for some C_d>0 and r_d ∈ [0, 1].

Then for any η>0 there exists a positive constant C_η such that, for any T sufficiently large, it holds that

    ℙ(
    	1  T∑_t=1^T  Z_t _2 > C_η √(d log (T)  T )) ≤1 T^η .





Let C^* denote a positive constant to be chosen below. Note that 

    ℙ( 1  T∑_t=1^T  Z_t _2 ≥ C^* √(d log (T)  T )) 
    	   ≤ d max_1 ≤ i ≤ dℙ( | ∑_t=1^T Z_i t| ≥  C^* √(T log (T) ))  .

Let ∑_t=1^T Z_i t = ∑_t=1^T Z'_i t + ∑_t=1^T Z”_i t where Z'_i t =  Z_i t1(|Z_i t| ≤ b_T) - 𝔼( Z_i t1(|Z_i t| ≤ b_T ) ) and 
Z”_i t  =  Z_i t1(|Z_i t| > b_T)    - 𝔼( Z_i t1(|Z_i t| > b_T) ).
Then we have

    ℙ( |  ∑_t=1^T Z_i t| >  C^* √(T log (T))) ≤ℙ( |∑_t=1^T Z'_i t| > C^* 2√(T log (T))) + ℙ( | ∑_t=1^T  Z”_i t| > C^*  2√(T log (T) ))  .

The sequence { Z'_i t}_t=1^T has the same mixing properties as { Z_t}_t=1^T and sup_1 ≤ i ≤ d Z_i t' _∞ < 2b_T. 
Define
ε_T = (C^*/2) √(T log (T) ),
b_T =   2 (r_d + 1/2 + η ) C^-1_m log(T) and 
M_T = ⌊ b_T^-1√(T / log (T))⌋.
For any T sufficiently large M_T ∈ [1,T] and 4 (2 b_T) M_T < ε_T, implying that 
the conditions of Theorem 2.1 of <cit.> are satisfied. Then we have

    ℙ( | ∑_t=1^T Z'_i t| > ε_T ) 
    	< 4 exp( - ε_T^2  64 T  M_T  D(T,M_T) + 16  3 b_T M_T ε_T ) + 4 T M_Texp( -C_α M_T^r_α)  ,

with D(T,M_T) =  sup_1≤ i≤ d𝔼[ ( ∑_t=1^M_T Z'_i t)^2 ].
Define γ(l) = sup_1≤ i≤ d |Cov(Z'_i t, Z'_i t+l)| for l=0,1,…
and note that D(T,M_T) ≤ M_T ∑_l=-M_T+1^M_T-1γ(l). 
For l=0,… it holds that 
γ(l) ≤ 12 α(l)^1  2sup_1≤ i ≤ d Z'_i t^2_L_4≤ 48 α(l)^1  2sup_1≤ i ≤ d Z_i t^2_L_4
where the first inequality follows from Davydov's inequality <cit.>
and the second one follows from the fact that Z_i t' _L_4≤ 2  Z_i t1(|Z_i t| ≤ b_T) _L_4≤ 2  Z_i t_L_4

This implies that D(T,M_T) < M_T C_σ^2 where C_σ^2 = ( 96 C_m,4∑_l = 0^∞α(l)^1  2 ) ∨ 1 where C_m,4 = sup_1≤ i ≤ d Z_i t^2_L_4.
We then have that 

    d max_1≤ i ≤ dℙ( | ∑_t=1^T Z'_i t| > ε_T ) 
    	≤ 4 C_d exp( r_d log (T) -  (C^*)^2 log (T)   256 C_σ^2 + 32  3 C^* ) + 4 C_d T^1+r_dexp( - C_α M_T^r_α) 
          < 4 C_d exp( -ηlog (T)  ) + 4 C_d exp( 2log(T) - C_α M_T^r_α)  
    	= 5 C_d  T^η ,

where the second inequality follows from a sufficiently large choice of the constant C^*.
The sequence { Z”_i t}_t=1^T is such that

    d max_1≤ i ≤ dℙ( | ∑_t=1^T Z”_i t| > ε_T) 
    	≤d ε_Tmax_1≤ i ≤ d𝔼| ∑_t=1^T Z”_i t|  
    	≤d ε_T∑_t=1^T max_1≤ i ≤ d𝔼 | Z”_i t |  
       ≤2dT ε_Tmax_1≤ i ≤ d𝔼| Z_i t1(|Z_i t| > b_T) | ≤2dT ε_Tmax_1≤ i ≤ d Z_i t_L_2 1( |Z_i t| > b_T  ) _L_2
        = 2dT ε_Tmax_1≤ i ≤ d Z_i t_L_2ℙ( |Z_i t| > b_T  )^1 2 < 2d T ε_Tσ^2 exp( -  C_m  2b_T  ) 
       ≤4 C_d σ^2  C^* √(log T )exp( (r_d + 1 2) log(T) - C_m  2 b_T) < 1  T^η ,

where the first inequality follows from Markov's inequality and σ^2 = sup_1≤ i ≤ d Z_i t_L_2. Equations (<ref>) and (<ref>) imply the claim.




natbib
 


