{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T23:06:17Z","timestamp":1777676777921,"version":"3.51.4"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,8,19]],"date-time":"2017-08-19T00:00:00Z","timestamp":1503100800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s10107-017-1182-z","type":"journal-article","created":{"date-parts":[[2017,8,19]],"date-time":"2017-08-19T01:01:54Z","timestamp":1503104514000},"page":"75-97","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Near-optimal stochastic approximation for online principal component estimation"],"prefix":"10.1007","volume":"167","author":[{"given":"Chris Junchi","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mengdi","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Han","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,19]]},"reference":[{"issue":"5","key":"1182_CR1","doi-asserted-by":"crossref","first-page":"3235","DOI":"10.1109\/TIT.2011.2182178","volume":"58","author":"A Agarwal","year":"2012","unstructured":"Agarwal, A., Bartlett, P., Ravikumar, P., Wainwright, M.: Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Trans. Inf. Theory 58(5), 3235\u20133249 (2012)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5B","key":"1182_CR2","doi-asserted-by":"crossref","first-page":"2877","DOI":"10.1214\/08-AOS664","volume":"37","author":"A Amini","year":"2009","unstructured":"Amini, A., Wainwright, M.: High-dimensional analysis of semidefinite relaxations for sparse principal components. Ann. Stat. 37(5B), 2877\u20132921 (2009)","journal-title":"Ann. Stat."},{"key":"1182_CR3","doi-asserted-by":"crossref","unstructured":"Arora, R., Cotter, A., Livescu, K., Srebro, N.: Stochastic optimization for PCA and PLS. In: 50th Annual Allerton Conference on Communication, Control, and Computing pp. 861\u2013868 (2012)","DOI":"10.1109\/Allerton.2012.6483308"},{"key":"1182_CR4","unstructured":"Arora, R., Cotter, A., Srebro, N.: Stochastic optimization of PCA with capped msg. In: Advances in Neural Information Processing Systems, pp. 1815\u20131823 (2013)"},{"key":"1182_CR5","first-page":"1","volume":"31","author":"K Ball","year":"1997","unstructured":"Ball, K.: An elementary introduction to modern convex geometry. Flavors Geom. 31, 1\u201358 (1997)","journal-title":"Flavors Geom."},{"key":"1182_CR6","unstructured":"Balsubramani, A., Dasgupta, S., Freund, Y.: The fast convergence of incremental PCA. In: Advances in Neural Information Processing Systems, pp. 3174\u20133182 (2013)"},{"key":"1182_CR7","volume-title":"Adaptive Algorithms and Stochastic Approximations","author":"A Benveniste","year":"2012","unstructured":"Benveniste, A., M\u00e9tivier, M., Priouret, P.: Adaptive Algorithms and Stochastic Approximations. Springer, New York (2012)"},{"key":"1182_CR8","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/s10107-011-0472-0","volume":"129","author":"D Bertsekas","year":"2011","unstructured":"Bertsekas, D.: Incremental proximal methods for large scale convex optimization. Math. Program. Ser. B 129, 163\u2013195 (2011)","journal-title":"Math. Program. Ser. B"},{"key":"1182_CR9","volume-title":"Parallel and Distributed Computation: Numerical Methods","author":"D Bertsekas","year":"1989","unstructured":"Bertsekas, D., Tsitsiklis, J.: Parallel and Distributed Computation: Numerical Methods. Athena Scientific, Belmont (1989)"},{"key":"1182_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-93-86279-38-5","volume-title":"Stochastic Approximation: A Dynamical Systems Viewpoint","author":"V Borkar","year":"2008","unstructured":"Borkar, V.: Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, Cambridge (2008)"},{"issue":"6","key":"1182_CR11","doi-asserted-by":"crossref","first-page":"3074","DOI":"10.1214\/13-AOS1178","volume":"41","author":"TT Cai","year":"2013","unstructured":"Cai, T.T., Ma, Z., Wu, Y.: Sparse PCA: optimal rates and adaptive estimation. Ann. Stat. 41(6), 3074\u20133110 (2013)","journal-title":"Ann. Stat."},{"key":"1182_CR12","first-page":"1269","volume":"9","author":"A d\u2019Aspremont","year":"2008","unstructured":"d\u2019Aspremont, A., Bach, F., El Ghaoui, L.: Optimal solutions for sparse principal component analysis. J. Mach. Learn. Res. 9, 1269\u20131294 (2008)","journal-title":"J. Mach. Learn. Res."},{"key":"1182_CR13","unstructured":"De\u00a0Sa, C., Olukotun, K., R\u00e9, C.: Global convergence of stochastic gradient descent for some non-convex matrix problems. In: Proceedings of The 32nd International Conference on Machine Learning, pp. 2332\u20132341 (2015)"},{"key":"1182_CR14","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511779398","volume-title":"Probability: Theory and Examples","author":"R Durrett","year":"2010","unstructured":"Durrett, R.: Probability: Theory and Examples, 4th edn. Cambridge University Press, Cambridge (2010)","edition":"4"},{"key":"1182_CR15","volume-title":"Markov Processes: Characterization and Convergence","author":"S\u00a0N Ethier","year":"2005","unstructured":"Ethier, S\u00a0.N., Kurtz, T\u00a0.G.: Markov Processes: Characterization and Convergence, vol. 282, 2nd edn. Wiley, Hoboken (2005)","edition":"2"},{"key":"1182_CR16","unstructured":"Garber, D., Hazan, E.: Fast and simple PCA via convex optimization. (2015). arXiv preprint \n                        arXiv:1509.05647"},{"key":"1182_CR17","unstructured":"Yang L, Braverman V, Zhao T, Wang M.: Dynamic factorization and partition of complex networks. \n                        arXiv:1705.07881"},{"key":"1182_CR18","unstructured":"Hardt, M., Price, E.: The noisy power method: A meta algorithm with applications. In: Advances in Neural Information Processing Systems, pp. 2861\u20132869 (2014a)"},{"key":"1182_CR19","unstructured":"Hardt, M., Price, E.: The Noisy Power Method: A Meta Algorithm with Applications. NIPS, pp. 2861\u20132869 (2014b)"},{"issue":"6","key":"1182_CR20","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1037\/h0071325","volume":"24","author":"H Hotelling","year":"1933","unstructured":"Hotelling, H.: Analysis of a complex of statistical variables into principal components. J. Educ. Psychol. 24(6), 417 (1933)","journal-title":"J. Educ. Psychol."},{"key":"1182_CR21","unstructured":"Jain, P., Jin, C., Kakade, S.M., Netrapalli, P., Sidford, A.: Matching matrix Bernstein with little memory: Near-optimal finite sample guarantees for Oja\u2019s algorithm (2016). arXiv preprint \n                        arXiv:1602.06929"},{"issue":"486","key":"1182_CR22","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1198\/jasa.2009.0121","volume":"104","author":"IM Johnstone","year":"2009","unstructured":"Johnstone, I.M., Lu, A.Y.: On consistency and sparsity for principal components analysis in high dimensions. J. Am. Stat. Assoc. 104(486), 682\u2013693 (2009)","journal-title":"J. Am. Stat. Assoc."},{"issue":"4","key":"1182_CR23","doi-asserted-by":"crossref","first-page":"1094","DOI":"10.1137\/0613066","volume":"13","author":"J Kuczynski","year":"1992","unstructured":"Kuczynski, J., Wozniakowski, H.: Estimating the largest eigenvalue by the power and lanczos algorithms with a random start. SIAM J. Matrix Anal. Appl. 13(4), 1094\u20131122 (1992)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1182_CR24","volume-title":"Stochastic Approximation and Recursive Algorithms and Applications","author":"H Kushner","year":"2003","unstructured":"Kushner, H., Yin, G.: Stochastic Approximation and Recursive Algorithms and Applications. Springer, New York (2003)"},{"issue":"2","key":"1182_CR25","doi-asserted-by":"crossref","first-page":"772","DOI":"10.1214\/13-AOS1097","volume":"41","author":"Z Ma","year":"2013","unstructured":"Ma, Z.: Sparse principal component analysis and iterative thresholding. Ann. Stat. 41(2), 772\u2013801 (2013)","journal-title":"Ann. Stat."},{"key":"1182_CR26","unstructured":"Mitliagkas, I., Caramanis, C., Jain, P.: Memory limited, streaming PCA. In: Advances in Neural Information Processing Systems, pp. 2886\u20132894 (2013)"},{"key":"1182_CR27","volume-title":"Aspects of Multivariate Statistical Theory","author":"R\u00a0J Muirhead","year":"2005","unstructured":"Muirhead, R\u00a0.J.: Aspects of Multivariate Statistical Theory, vol. 197. Wiley, Hoboken (2005)"},{"key":"1182_CR28","unstructured":"Musco, C., Musco, C.: Stronger approximate singular value decomposition via the block lanczos and power methods (2015). arXiv preprint \n                        arXiv:1504.05477"},{"issue":"2","key":"1182_CR29","doi-asserted-by":"crossref","first-page":"2791","DOI":"10.1214\/08-AOS618","volume":"41","author":"B Nadler","year":"2008","unstructured":"Nadler, B.: Finite sample approximation results for principal component analysis: a matrix perturbation approach. Ann. Stat. 41(2), 2791\u20132817 (2008)","journal-title":"Ann. Stat."},{"key":"1182_CR30","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s10107-011-0468-9","volume":"129","author":"A Nedi\u0107","year":"2011","unstructured":"Nedi\u0107, A.: Random algorithms for convex minimization problems. Math. Program. Ser. B 129, 225\u2013253 (2011)","journal-title":"Math. Program. Ser. B"},{"key":"1182_CR31","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1137\/S1052623499362111","volume":"12","author":"A Nedi\u0107","year":"2001","unstructured":"Nedi\u0107, A., Bertsekas, D.: Incremental subgradient methods for nondifferentiable optimization. SIAM J. Optim. 12, 109\u2013138 (2001)","journal-title":"SIAM J. Optim."},{"key":"1182_CR32","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/S1570-579X(01)80023-9","volume":"8","author":"A Nedi\u0107","year":"2001","unstructured":"Nedi\u0107, A., Bertsekas, D., Borkar, V.: Distributed asynchronous incremental subgradient methods. Stud. Comput. Math. 8, 381\u2013407 (2001)","journal-title":"Stud. Comput. Math."},{"key":"1182_CR33","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"A Nemirovsky","year":"1983","unstructured":"Nemirovsky, A., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley, Hoboken (1983)"},{"issue":"3","key":"1182_CR34","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/BF00275687","volume":"15","author":"E Oja","year":"1982","unstructured":"Oja, E.: Simplified neuron model as a principal component analyzer. J. Math. Biol. 15(3), 267\u2013273 (1982)","journal-title":"J. Math. Biol."},{"issue":"1","key":"1182_CR35","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0022-247X(85)90131-3","volume":"106","author":"E Oja","year":"1985","unstructured":"Oja, E., Karhunen, J.: On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix. J. Math. Anal. Appl. 106(1), 69\u201384 (1985)","journal-title":"J. Math. Anal. Appl."},{"issue":"11","key":"1182_CR36","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1080\/14786440109462720","volume":"2","author":"K Pearson","year":"1901","unstructured":"Pearson, K.: Liii. on lines and planes of closest fit to systems of points in space. Lond. Edinb. Dublin Philos. Mag. J. Sci. 2(11), 559\u2013572 (1901)","journal-title":"Lond. Edinb. Dublin Philos. Mag. J. Sci."},{"key":"1182_CR37","unstructured":"Rakhlin, A., Shamir, O., Sridharan, K.: Making gradient descent optimal for strongly convex stochastic optimization. In: Proceedings of the 29th International Conference on Machine Learning, pp. 449\u2013456 (2012)"},{"key":"1182_CR38","unstructured":"Sa, C.D., Re, C., Olukotun, K.: Global convergence of stochastic gradient descent for some non-convex matrix problems. In: Proceedings of the 32nd International Conference on Machine Learning (ICML-15), pp. 2332\u20132341 (2015)"},{"key":"1182_CR39","unstructured":"Shamir, O.: Convergence of stochastic gradient descent for PCA (2015a). arXiv preprint \n                        arXiv:1509.09002"},{"key":"1182_CR40","unstructured":"Shamir, O.: Fast stochastic algorithms for svd and PCA: Convergence properties and convexity (2015b). arXiv preprint \n                        arXiv:1507.08788"},{"key":"1182_CR41","unstructured":"Shamir, O.: A stochastic PCA and svd algorithm with an exponential convergence rate. In: Proceedings of the 32nd International Conference on Machine Learning (ICML-15), pp. 144\u2013152 (2015c)"},{"key":"1182_CR42","unstructured":"Shamir, O., Zhang, T.: Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In: Proceedings of The 30th International Conference on Machine Learning, pp. 71\u201379 (2013)"},{"key":"1182_CR43","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2545-2","volume-title":"Weak Convergence and Empirical Processes","author":"A\u00a0W Vaart Van Der","year":"1996","unstructured":"Van Der Vaart, A\u00a0.W., Wellner, J\u00a0.A.: Weak Convergence and Empirical Processes. Springer, New York (1996)"},{"key":"1182_CR44","doi-asserted-by":"crossref","unstructured":"Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. In: Compressed sensing. Cambridge University Press, pp. 210\u2013268 (2012)","DOI":"10.1017\/CBO9780511794308.006"},{"key":"1182_CR45","unstructured":"Vu, V.Q., Lei, J.: Minimax Rates of Estimation for Sparse PCA in High Dimensions. AISTATS, pp. 1278\u20131286 (2012)"},{"issue":"6","key":"1182_CR46","doi-asserted-by":"crossref","first-page":"2905","DOI":"10.1214\/13-AOS1151","volume":"41","author":"VQ Vu","year":"2013","unstructured":"Vu, V.Q., Lei, J.: Minimax sparse principal subspace estimation in high dimensions. Ann. Stat. 41(6), 2905\u20132947 (2013)","journal-title":"Ann. Stat."},{"key":"1182_CR47","unstructured":"Wang, M., Bertsekas, D.: Incremental constraint projection methods for variational inequalities. Math. Program. Ser. A, 1\u201343 (2014a)"},{"issue":"1","key":"1182_CR48","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1137\/130931278","volume":"26","author":"M Wang","year":"2016","unstructured":"Wang, M., Bertsekas, D.P.: Stochastic first-order methods with random constraint projection. SIAM J. Optim. 26(1), 681\u2013717 (2016)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1182_CR49","first-page":"419","volume":"161","author":"M Wang","year":"2016","unstructured":"Wang, M., Fang, X., Liu, H.: Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Math. Prog. 161(1), 419\u2013449 (2016)","journal-title":"Math. Prog."},{"key":"1182_CR50","unstructured":"Wang, Z., Lu, H., Liu, H.: Nonconvex statistical optimization: minimax-optimal sparse PCA in polynomial time. (2014b). arXiv preprint \n                        arXiv:1408.5352"},{"issue":"1","key":"1182_CR51","first-page":"899","volume":"14","author":"X-T Yuan","year":"2013","unstructured":"Yuan, X.-T., Zhang, T.: Truncated power method for sparse eigenvalue problems. J. Mach. Learn. Res. 14(1), 899\u2013925 (2013)","journal-title":"J. Mach. Learn. Res."},{"issue":"476","key":"1182_CR52","doi-asserted-by":"crossref","first-page":"1418","DOI":"10.1198\/016214506000000735","volume":"101","author":"H Zou","year":"2006","unstructured":"Zou, H.: The adaptive lasso and its oracle properties. J. Am. Stat. Assoc. 101(476), 1418\u20131429 (2006)","journal-title":"J. Am. Stat. Assoc."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-017-1182-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1182-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1182-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,1,19]],"date-time":"2018-01-19T05:39:24Z","timestamp":1516340364000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-017-1182-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,19]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["1182"],"URL":"https:\/\/doi.org\/10.1007\/s10107-017-1182-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,19]]}}}