{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T20:40:03Z","timestamp":1749588003545,"version":"3.41.0"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319463780"},{"type":"electronic","value":"9783319463797"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-46379-7_6","type":"book-chapter","created":{"date-parts":[[2016,9,20]],"date-time":"2016-09-20T10:54:33Z","timestamp":1474368873000},"page":"83-97","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Sparse Learning for Large-Scale and High-Dimensional Data: A Randomized Convex-Concave Optimization Approach"],"prefix":"10.1007","author":[{"given":"Lijun","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tianbao","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rong","family":"Jin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhi-Hua","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,21]]},"reference":[{"issue":"4","key":"6_CR1","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0022-0000(03)00025-4","volume":"66","author":"D Achlioptas","year":"2003","unstructured":"Achlioptas, D.: Database-friendly random projections: Johnson-lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4), 671\u2013687 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"6_CR2","doi-asserted-by":"publisher","first-page":"2452","DOI":"10.1214\/12-AOS1032","volume":"40","author":"A Agarwal","year":"2012","unstructured":"Agarwal, A., Negahban, S., Wainwright, M.J.: Fast global convergence of gradient methods for high-dimensional statistical recovery. Ann. Stat. 40(5), 2452\u20132482 (2012)","journal-title":"Ann. Stat."},{"issue":"2","key":"6_CR3","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s10994-006-6265-7","volume":"63","author":"RI Arriaga","year":"2006","unstructured":"Arriaga, R.I., Vempala, S.: An algorithmic theory of learning: robust concepts and random projection. Mach. Learn. 63(2), 161\u2013182 (2006)","journal-title":"Mach. Learn."},{"issue":"1","key":"6_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000015","volume":"4","author":"F Bach","year":"2012","unstructured":"Bach, F., Jenatton, R., Mairal, J., Obozinski, G.: Optimization with sparsity-inducing penalties. Found. Trends Mach. Learn. 4(1), 1\u2013106 (2012)","journal-title":"Found. Trends Mach. Learn."},{"issue":"1","key":"6_CR5","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10994-006-7550-1","volume":"65","author":"MF Balcan","year":"2006","unstructured":"Balcan, M.F., Blum, A., Vempala, S.: Kernels as features: on kernels, margins, and low-dimensional mappings. Mach. Learn. 65(1), 79\u201394 (2006)","journal-title":"Mach. Learn."},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Bingham, E., Mannila, H.: Random projection in dimensionality reduction: applications to image and text data. In: Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 245\u2013250 (2001)","DOI":"10.1145\/502512.502546"},{"key":"6_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"issue":"9\u201310","key":"6_CR8","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1016\/j.crma.2008.03.014","volume":"346","author":"EJ Cand\u00e8s","year":"2008","unstructured":"Cand\u00e8s, E.J.: The restricted isometry property and its implications for compressed sensing. C.R. Math. 346(9\u201310), 589\u2013592 (2008)","journal-title":"C.R. Math."},{"key":"6_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546921","volume-title":"Prediction, Learning, and Games","author":"N Cesa-Bianchi","year":"2006","unstructured":"Cesa-Bianchi, N., Lugosi, G.: Prediction, Learning, and Games. Cambridge University Press, Cambridge (2006)"},{"issue":"1","key":"6_CR10","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s10851-010-0251-1","volume":"40","author":"A Chambolle","year":"2011","unstructured":"Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120\u2013145 (2011)","journal-title":"J. Math. Imaging Vis."},{"issue":"1","key":"6_CR11","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1002\/rsa.10073","volume":"22","author":"S Dasgupta","year":"2003","unstructured":"Dasgupta, S., Gupta, A.: An elementary proof of a theorem of Johnson and lindenstrauss. Random Struct. Algorithms 22(1), 60\u201365 (2003)","journal-title":"Random Struct. Algorithms"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Davenport, M.A., Duarte, M.F., Eldar, Y.C., Kutyniok, G.: Introduction to compressed sensing (chap. 1). In: Compressed Sensing, Theory and Applications, pp. 1\u201364. Cambridge University Press (2012)","DOI":"10.1017\/CBO9780511794308.002"},{"key":"6_CR13","series-title":"Springer Series in Statistics","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-84858-7","volume-title":"The Elements of Statistical Learning","author":"T Hastie","year":"2009","unstructured":"Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning. Springer Series in Statistics. Springer, New York (2009)"},{"key":"6_CR14","unstructured":"He, Y., Monteiro, R.D.: An accelerated hpe-type algorithm for a class of composite convex-concave saddle-point problems. Technical report, Georgia Institute of Technology (2014)"},{"key":"6_CR15","unstructured":"Kakade, S.M., Shalev-Shwartz, S., Tewari, A.: On the duality of strong convexity and strong smoothness: learning applications and matrix regularization. Technical report, Toyota Technological Institute at Chicago (2009)"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Kaski, S.: Dimensionality reduction by random mapping: fast similarity computation for clustering. In: Proceedings of the 1998 IEEE International Joint Conference on Neural Networks, vol. 1, pp. 413\u2013418 (1998)","DOI":"10.1109\/IJCNN.1998.682302"},{"key":"6_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22147-7","volume-title":"Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems","author":"V Koltchinskii","year":"2011","unstructured":"Koltchinskii, V.: Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems. Springer, Heidelberg (2011)"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/3-540-45726-7_19","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"A Magen","year":"2002","unstructured":"Magen, A.: Dimensionality reductions that preserve volumes and distance to affine spaces, and their algorithmic applications. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol. 2483, pp. 239\u2013253. Springer, Heidelberg (2002)"},{"issue":"2","key":"6_CR19","first-page":"123","volume":"3","author":"MW Mahoney","year":"2011","unstructured":"Mahoney, M.W.: Randomized algorithms for matrices and data. Found. Trends Mach. Learn. 3(2), 123\u2013224 (2011)","journal-title":"Found. Trends Mach. Learn."},{"issue":"3","key":"6_CR20","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s00365-007-9005-8","volume":"28","author":"S Mendelson","year":"2008","unstructured":"Mendelson, S., Pajor, A., Tomczak-Jaegermann, N.: Uniform uncertainty principle for Bernoulli and subgaussian ensembles. Constr. Approximation 28(3), 277\u2013289 (2008)","journal-title":"Constr. Approximation"},{"issue":"1","key":"6_CR21","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1137\/S1052623403425629","volume":"15","author":"A Nemirovski","year":"2005","unstructured":"Nemirovski, A.: Prox-method with rate of convergence $${O}(1\/t)$$ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1), 229\u2013251 (2005)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"6_CR22","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","volume":"103","author":"Y Nesterov","year":"2005","unstructured":"Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103(1), 127\u2013152 (2005)","journal-title":"Math. Program."},{"key":"6_CR23","first-page":"2361","volume":"11","author":"D Omidiran","year":"2010","unstructured":"Omidiran, D., Wainwright, M.J.: High-dimensional variable selection with sparse random projections: measurement sparsity and statistical efficiency. J. Mach. Learn. Res. 11, 2361\u20132386 (2010)","journal-title":"J. Mach. Learn. Res."},{"key":"6_CR24","unstructured":"Paul, S., Boutsidis, C., Magdon-Ismail, M., Drineas, P.: Random projections for support vector machines. In: Proceedings of the 16th International Conference on Artificial Intelligence and Statistics, pp. 498\u2013506 (2013)"},{"issue":"8","key":"6_CR25","doi-asserted-by":"publisher","first-page":"1275","DOI":"10.1002\/cpa.21442","volume":"66","author":"Y Plan","year":"2013","unstructured":"Plan, Y., Vershynin, R.: One-bit compressed sensing by linear programming. Commun. Pure Appl. Math. 66(8), 1275\u20131297 (2013)","journal-title":"Commun. Pure Appl. Math."},{"issue":"1","key":"6_CR26","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1109\/TIT.2012.2207945","volume":"59","author":"Y Plan","year":"2013","unstructured":"Plan, Y., Vershynin, R.: Robust 1-bit compressed sensing and sparse logistic regression: a convex programming approach. IEEE Trans. Inf. Theor. 59(1), 482\u2013494 (2013)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"6_CR27","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"1997","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1997)"},{"key":"6_CR28","unstructured":"Shi, Q., Shen, C., Hill, R., van den Hengel, A.: Is margin preserved after random projection? In: Proceedings of the 29th International Conference on Machine Learning (2012)"},{"key":"6_CR29","first-page":"1545","volume":"21","author":"K Sridharan","year":"2009","unstructured":"Sridharan, K., Shalev-shwartz, S., Srebro, N.: Fast rates for regularized objectives. Adv. Neural Inf. Process. Syst. 21, 1545\u20131552 (2009)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"6_CR30","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s10208-011-9099-z","volume":"12","author":"JA Tropp","year":"2012","unstructured":"Tropp, J.A.: User-friendly tail bounds for sums of random matrices. Found. Comput. Math. 12, 389\u2013434 (2012)","journal-title":"Found. Comput. Math."},{"key":"6_CR31","first-page":"1453","volume":"6","author":"I Tsochantaridis","year":"2005","unstructured":"Tsochantaridis, I., Joachims, T., Hofmann, T., Altun, Y.: Large margin methods for structured and interdependent output variables. J. Mach. Learn. Res. 6, 1453\u20131484 (2005)","journal-title":"J. Mach. Learn. Res."},{"issue":"5","key":"6_CR32","doi-asserted-by":"publisher","first-page":"1160","DOI":"10.1162\/0899766053491896","volume":"17","author":"Q Wu","year":"2005","unstructured":"Wu, Q., Zhou, D.X.: Svm soft margin classifiers: linear programming versus quadratic programming. Neural Comput. 17(5), 1160\u20131187 (2005)","journal-title":"Neural Comput."},{"key":"6_CR33","unstructured":"Xiao, L., Zhang, T.: A proximal-gradient homotopy method for the $$\\ell _1$$-regularized least-squares problem. In: Proceedings of the 29th International Conference on Machine Learning, pp. 839\u2013846 (2012)"},{"key":"6_CR34","unstructured":"Yang, T., Zhang, L., Jin, R., Zhu, S.: Theory of dual-sparse regularized randomized reduction. In: Proceedings of the 32nd International Conference on Machine Learning (2015)"},{"key":"6_CR35","unstructured":"Zhang, L., Mahdavi, M., Jin, R., Yang, T., Zhu, S.: Recovering the optimal solution by dual random projection. In: Proceedings of the 26th Annual Conference on Learning Theory (COLT), pp. 135\u2013157 (2013)"},{"issue":"11","key":"6_CR36","doi-asserted-by":"publisher","first-page":"7300","DOI":"10.1109\/TIT.2014.2359204","volume":"60","author":"L Zhang","year":"2014","unstructured":"Zhang, L., Mahdavi, M., Jin, R., Yang, T., Zhu, S.: Random projections for classification: a recovery approach. IEEE Trans. Inf. Theor. 60(11), 7300\u20137316 (2014)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"6_CR37","unstructured":"Zhang, L., Yang, T., Jin, R., Zhou, Z.H.: A simple homotopy algorithm for compressive sensing. In: Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (2015)"},{"issue":"2","key":"6_CR38","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1111\/j.1467-9868.2005.00503.x","volume":"67","author":"H Zou","year":"2005","unstructured":"Zou, H., Hastie, T.: Regularization and variable selection via the elastic net. J. Roy. Stat. Soc. Series B (Stat. Methodol.) 67(2), 301\u2013320 (2005)","journal-title":"J. Roy. Stat. Soc. Series B (Stat. Methodol.)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-46379-7_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T20:14:48Z","timestamp":1749586488000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-46379-7_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319463780","9783319463797"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-46379-7_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"21 September 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ALT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithmic Learning Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bari","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 October 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 October 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"alt2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}