{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T12:23:44Z","timestamp":1709382224442},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2015,7,5]],"date-time":"2015-07-05T00:00:00Z","timestamp":1436054400000},"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":["Math. Program."],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s10107-015-0932-z","type":"journal-article","created":{"date-parts":[[2015,7,4]],"date-time":"2015-07-04T10:45:07Z","timestamp":1436006707000},"page":"329-361","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Sublinear time algorithms for approximate semidefinite programming"],"prefix":"10.1007","volume":"158","author":[{"given":"Dan","family":"Garber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elad","family":"Hazan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,5]]},"reference":[{"key":"932_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, A., Charikar, M., Makarychev, K., Makarychev, Y.: O(sqrt(log n)) approximation algorithms for min uncut, min 2cnf deletion, and directed cut problems. In: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, STOC \u201905, pp. 573\u2013581 (2005)","DOI":"10.1145\/1060590.1060675"},{"issue":"1","key":"932_CR2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theory Comput. 8(1), 121\u2013164 (2012)","journal-title":"Theory Comput."},{"key":"932_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. In: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, STOC \u201905, pp. 553\u2013562 (2005)","DOI":"10.1145\/1060590.1060673"},{"key":"932_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. In: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, STOC \u201904, pp. 222\u2013231 (2004)","DOI":"10.1145\/1007352.1007355"},{"issue":"2","key":"932_CR5","doi-asserted-by":"crossref","first-page":"934","DOI":"10.1137\/11085801X","volume":"23","author":"M Baes","year":"2013","unstructured":"Baes, M., B\u00fcrgisser, M., Nemirovski, A.: A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems. SIAM J. Optim. 23(2), 934\u2013962 (2013)","journal-title":"SIAM J. Optim."},{"key":"932_CR6","doi-asserted-by":"crossref","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)"},{"key":"932_CR7","doi-asserted-by":"crossref","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, New York, NY (2006)"},{"issue":"5","key":"932_CR8","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/2371656.2371658","volume":"59","author":"KL Clarkson","year":"2012","unstructured":"Clarkson, K.L., Hazan, E., Woodruff, D.P.: Sublinear optimization for machine learning. J. ACM 59(5), 23 (2012)","journal-title":"J. ACM"},{"key":"932_CR9","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1214\/10-SSY018","volume":"1","author":"AW D\u2019Aspremont","year":"2011","unstructured":"D\u2019Aspremont, A.W.: Subsampling algorithms for semidefinite programming. Stoch. Syst. 1, 274\u2013305 (2011). doi: 10.1214\/10-SSY018","journal-title":"Stoch. Syst."},{"key":"932_CR10","first-page":"41","volume":"3","author":"A d\u2019Aspremont","year":"2004","unstructured":"d\u2019Aspremont, A., Ghaoui, L.E., Jordan, M.I., Lanckriet, G.R.G.: A direct formulation of sparse PCA using semidefinite programming. SIAM Rev. 3, 41\u201348 (2004)","journal-title":"SIAM Rev."},{"key":"932_CR11","unstructured":"Garber, D., Hazan, E.: Approximating semidefinite programs in sublinear time. In: NIPS, pp. 1080\u20131088 (2011)"},{"key":"932_CR12","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"2","key":"932_CR13","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0167-6377(95)00032-0","volume":"18","author":"MD Grigoriadis","year":"1995","unstructured":"Grigoriadis, M.D., Khachiyan, L.G.: A sublinear-time randomized approximation algorithm for matrix games. Oper. Res. Lett. 18(2), 53\u201358 (1995)","journal-title":"Oper. Res. Lett."},{"key":"932_CR14","unstructured":"Hazan, E.: Approximate convex optimization by online game playing. CoRR. arXiv:0610119 (2006)"},{"key":"932_CR15","doi-asserted-by":"crossref","unstructured":"Hazan, E.: Sparse approximate solutions to semidefinite programs. In: Proceedings of the 8th Latin American conference on Theoretical informatics, LATIN\u201908, pp. 306\u2013316 (2008)","DOI":"10.1007\/978-3-540-78773-0_27"},{"key":"932_CR16","doi-asserted-by":"crossref","unstructured":"Sra, S., Nowozin, S., Wright, S.J.: Optimization for machine learning. MIT Press (2012)","DOI":"10.7551\/mitpress\/8996.001.0001"},{"issue":"1","key":"932_CR17","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1214\/10-SSY011","volume":"1","author":"A Juditsky","year":"2011","unstructured":"Juditsky, A., Nemirovski, A., Tauvel, C.: Solving variational inequalities with stochastic mirror-prox algorithm. Stoch. Syst. 1(1), 17\u201358 (2011). doi: 10.1214\/10-SSY011","journal-title":"Stoch. Syst."},{"key":"932_CR18","doi-asserted-by":"crossref","first-page":"1094","DOI":"10.1137\/0613066","volume":"13","author":"J Kuczy\u0144ski","year":"1992","unstructured":"Kuczy\u0144ski, J., Wo\u017aniakowski, H.: Estimating the largest eigenvalues by the power and lanczos algorithms with a random start. SIAM J. Matrix Anal. Appl. 13, 1094\u20131122 (1992)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"932_CR19","unstructured":"Lanckriet, G.R.G., Cristianini, N., Ghaoui, L.E., Bartlett, P., Jordan, M.I.: Learning the kernel matrix with semi-definite programming. In: Journal of Machine Learning Research, pp. 27\u201372 (2004)"},{"issue":"1","key":"932_CR20","doi-asserted-by":"crossref","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":"2","key":"932_CR21","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s10107-006-0001-8","volume":"110","author":"Y Nesterov","year":"2007","unstructured":"Nesterov, Y.: Smoothing technique and its applications in semidefinite optimization. Math. Program. 110(2), 245\u2013259 (2007)","journal-title":"Math. Program."},{"key":"932_CR22","first-page":"3413","volume":"12","author":"B Recht","year":"2011","unstructured":"Recht, B.: A simpler approach to matrix completion. J. Mach. Learn. Res. 12, 3413\u20133430 (2011)","journal-title":"J. Mach. Learn. Res."},{"issue":"2","key":"932_CR23","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1561\/2200000018","volume":"4","author":"S Shalev-Shwartz","year":"2012","unstructured":"Shalev-Shwartz, S.: Online learning and online convex optimization. Found. Trend. Mach. Learn. 4(2), 107\u2013194 (2012)","journal-title":"Found. Trend. Mach. Learn."},{"key":"932_CR24","doi-asserted-by":"crossref","unstructured":"Shalev-shwartz, S., Singer, Y., Ng, A.Y.: Online and batch learning of pseudo-metrics. In: ICML, pp. 743\u2013750 (2004)","DOI":"10.1145\/1015330.1015376"},{"issue":"4","key":"932_CR25","doi-asserted-by":"crossref","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(4), 389\u2013434 (2012)","journal-title":"Found. Comput. Math."},{"key":"932_CR26","first-page":"505","volume":"15","author":"EP Xing","year":"2002","unstructured":"Xing, E.P., Ng, A.Y., Jordan, M.I., Russell, S.: Distance metric learning, with application to clustering with side-information. Adv. Neural Inf. Process. Syst. 15, 505\u2013512 (2002)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"932_CR27","unstructured":"Zinkevich, M.: Online convex programming and generalized infinitesimal gradient ascent. In: ICML, pp. 928\u2013936 (2003)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0932-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-015-0932-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0932-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,28]],"date-time":"2019-08-28T00:08:06Z","timestamp":1566950886000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-015-0932-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,5]]},"references-count":27,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["932"],"URL":"https:\/\/doi.org\/10.1007\/s10107-015-0932-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,5]]}}}