7a006957be65e608e863301eb98e1808-Supplemental.pdf

In Appendix A, we review some statistical results for sparse linear regression. In Appendix B, we provide the proof of main theorems as well as main claims. We review some classical results in sparse linear regression. B.1 Proof of Claim 3.5 We first prove the first part. Combining with Eq. (B.6), we have under event D B.2 Proof of Claim 3.6 From the divergence decomposition lemma (Lemma C.2 in the appendix), we have KLnull P To prove the claim, we use a simple argument "minimum is always smaller than the average".