Optimal rates of convergence for sparse covariance matrix estimation. (English) Zbl 1373.62247

Summary: This paper considers estimation of sparse covariance matrices and establishes the optimal rate of convergence under a range of matrix operator norm and Bregman divergence losses. A major focus is on the derivation of a rate sharp minimax lower bound. The problem exhibits new features that are significantly different from those that occur in the conventional nonparametric function estimation problems. Standard techniques fail to yield good results, and new tools are thus needed. { } We first develop a lower bound technique that is particularly well suited for treating “two-directional” problems such as estimating sparse covariance matrices. The result can be viewed as a generalization of Le Cam’s method in one direction and Assouad’s Lemma in another. This lower bound technique is of independent interest and can be used for other matrix estimation problems. { } We then establish a rate sharp minimax lower bound for estimating sparse covariance matrices under the spectral norm by applying the general lower bound technique. A thresholding estimator is shown to attain the optimal rate of convergence under the spectral norm. The results are then extended to the general matrix \(\ell_{w}\) operator norms for \(1\leq w\leq\infty\). In addition, we give a unified result on the minimax rate of convergence for sparse covariance matrix estimation under a class of Bregman divergence losses.


62H12 Estimation in multivariate analysis
62F12 Asymptotic properties of parametric estimators
Full Text: DOI arXiv Euclid


[1] Abramovich, F., Benjamini, Y., Donoho, D. L. and Johnstone, I. M. (2006). Adapting to unknown sparsity by controlling the false discovery rate. Ann. Statist. 34 584-653. · Zbl 1092.62005 · doi:10.1214/009053606000000074
[2] Assouad, P. (1983). Deux remarques sur l’estimation. C. R. Acad. Sci. Paris Sér. I Math. 296 1021-1024. · Zbl 0568.62003
[3] Bickel, P. J. and Levina, E. (2008a). Regularized estimation of large covariance matrices. Ann. Statist. 36 199-227. · Zbl 1132.62040 · doi:10.1214/009053607000000758
[4] Bickel, P. J. and Levina, E. (2008b). Covariance regularization by thresholding. Ann. Statist. 36 2577-2604. · Zbl 1196.62062 · doi:10.1214/08-AOS600
[5] Brègman, L. M. (1967). A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7 200-217. · Zbl 0186.23807
[6] Cai, T. and Liu, W. (2011). Adaptive thresholding for sparse covariance matrix estimation. J. Amer. Statist. Assoc. 106 672-684. · Zbl 1232.62086 · doi:10.1198/jasa.2011.tm10560
[7] Cai, T. T., Liu, W. and Zhou, H. H. (2011). Optimal estimation of large sparse precision matrices. Unpublished manuscript.
[8] Cai, T. T., Zhang, C.-H. and Zhou, H. H. (2010). Optimal rates of convergence for covariance matrix estimation. Ann. Statist. 38 2118-2144. · Zbl 1202.62073 · doi:10.1214/09-AOS752
[9] Cai, T. T. and Zhou, H. H. (2009). Covariance matrix estimation under the \(\ell_1\) norm (with discussion). Statist. Sinica 22 1319-1378.
[10] Cai, T. T. and Zhou, H. H. (2012). Supplement to “Optimal rates of convergence for sparse covariance matrix estimation.” . · Zbl 1373.62247
[11] Censor, Y. and Zenios, S. A. (1997). Parallel Optimization : Theory , Algorithms , and Applications . Oxford Univ. Press, New York. · Zbl 0945.90064
[12] Dhillon, I. S. and Tropp, J. A. (2007). Matrix nearness problems with Bregman divergences. SIAM J. Matrix Anal. Appl. 29 1120-1146. · Zbl 1153.65044 · doi:10.1137/060649021
[13] Donoho, D. L. and Liu, R. C. (1991). Geometrizing rates of convergence. II. Ann. Statist. 19 633-667. · Zbl 0754.62028 · doi:10.1214/aos/1176348114
[14] El Karoui, N. (2008). Operator norm consistent estimation of large-dimensional sparse covariance matrices. Ann. Statist. 36 2717-2756. · Zbl 1196.62064 · doi:10.1214/07-AOS559
[15] Kulis, B., Sustik, M. A. and Dhillon, I. S. (2009). Low-rank kernel learning with Bregman matrix divergences. J. Mach. Learn. Res. 10 341-376. · Zbl 1235.68166
[16] Lam, C. and Fan, J. (2009). Sparsistency and rates of convergence in large covariance matrix estimation. Ann. Statist. 37 4254-4278. · Zbl 1191.62101 · doi:10.1214/09-AOS720
[17] Le Cam, L. (1973). Convergence of estimates under dimensionality restrictions. Ann. Statist. 1 38-53. · Zbl 0255.62006 · doi:10.1214/aos/1193342380
[18] Le Cam, L. (1986). Asymptotic Methods in Statistical Decision Theory . Springer, New York. · Zbl 0605.62002
[19] Ravikumar, P., Wainwright, M., Raskutti, G. and Yu, B. (2008). High-dimensional covariance estimation by minimizing \(l_1\)-penalized log-determinant divergence. Technical Report 797, Dept. Statistics, UC Berkeley. · Zbl 1274.62190
[20] Rothman, A. J., Levina, E. and Zhu, J. (2009). Generalized thresholding of large covariance matrices. J. Amer. Statist. Assoc. 104 177-186. · Zbl 1388.62170 · doi:10.1198/jasa.2009.0101
[21] Saulis, L. and Statulevičius, V. A. (1991). Limit Theorems for Large Deviations. Mathematics and Its Applications ( Soviet Series ) 73 . Kluwer Academic, Dordrecht. · Zbl 0744.60028
[22] Tsybakov, A. B. (2009). Introduction to Nonparametric Estimation . Springer, New York. · Zbl 1176.62032
[23] van der Vaart, A. W. (1998). Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics 3 . Cambridge Univ. Press, Cambridge. · Zbl 0910.62001 · doi:10.1017/CBO9780511802256
[24] Whittle, P. (1960). Bounds for the moments of linear and quadratic forms in independent variables. Theory Probab. Appl. 5 302-305. · Zbl 0101.12003
[25] Yu, B. (1997). Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam (D. Pollard, E. Torgersen and G. Yang, eds.) 423-435. Springer, New York. · Zbl 0896.62032 · doi:10.1007/978-1-4612-1880-7_29
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.