{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T18:29:05Z","timestamp":1780338545956,"version":"3.54.1"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T00:00:00Z","timestamp":1578614400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T00:00:00Z","timestamp":1578614400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"National Science Foundation","award":["CCF-1563918"],"award-info":[{"award-number":["CCF-1563918"]}]},{"name":"National Science Foundation","award":["IIS-1252412"],"award-info":[{"award-number":["IIS-1252412"]}]},{"DOI":"10.13039\/100006602","name":"Air Force Research Laboratory","doi-asserted-by":"publisher","award":["FA87501720212"],"award-info":[{"award-number":["FA87501720212"]}],"id":[{"id":"10.13039\/100006602","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,3]]},"DOI":"10.1007\/s10107-019-01464-2","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T15:17:40Z","timestamp":1578669460000},"page":"439-478","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Near-optimal discrete optimization for experimental design: a regret minimization approach"],"prefix":"10.1007","volume":"186","author":[{"given":"Zeyuan","family":"Allen-Zhu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuanzhi","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aarti","family":"Singh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yining","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,1,10]]},"reference":[{"issue":"3","key":"1464_CR1","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"AA Ageev","year":"2004","unstructured":"Ageev, A.A., Sviridenko, M.I.: Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8(3), 307\u2013328 (2004)","journal-title":"J. Comb. Optim."},{"key":"1464_CR2","unstructured":"Allen-Zhu, Z., Li, Y.: Follow the compressed leader: faster online learning of eigenvectors and faster MMWU. In: Proceedings of the International Conference on Machine Learning (ICML). Full version available at arxiv:1701.01722 (2017)"},{"key":"1464_CR3","unstructured":"Allen-Zhu, Z., Li, Y., Singh, A., Wang, Y.: Near-optimal design of experiments via regret minimization. In: Proceedings of the International Conference on Machine Learning (ICML), (2017)"},{"key":"1464_CR4","doi-asserted-by":"crossref","unstructured":"Allen-Zhu, Z., Liao, Z., Orecchia, L.: Spectral sparsification and regret minimization beyond matrix multiplicative updates. In: Proceedings of Annual Symposium on the Theory of Computing (STOC), (2015)","DOI":"10.1145\/2746539.2746610"},{"issue":"4","key":"1464_CR5","first-page":"319","volume":"2","author":"D Angluin","year":"1988","unstructured":"Angluin, D.: Queries and concept learning. Mach. Learn. 2(4), 319\u2013342 (1988)","journal-title":"Mach. Learn."},{"key":"1464_CR6","doi-asserted-by":"crossref","unstructured":"Arora, S., Kale, S.: A combinatorial, primal-dual approach to semidefinite programs. In: Proceedings of the annual ACM Symposium on Theory of Computing (STOC), (2007)","DOI":"10.1145\/1250790.1250823"},{"key":"1464_CR7","unstructured":"Audibert, J.-Y., Bubeck, S., Lugosi, G.: Minimax policies for combinatorial prediction games. In: Proceedings of Conference on Learning Theory (COLT), (2011)"},{"issue":"4","key":"1464_CR8","doi-asserted-by":"publisher","first-page":"1464","DOI":"10.1137\/120867287","volume":"34","author":"H Avron","year":"2013","unstructured":"Avron, H., Boutsidis, C.: Faster subset selection for matrices and applications. SIAM J. Matrix Anal. Appl. 34(4), 1464\u20131499 (2013)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1464_CR9","unstructured":"Bach, F.: Submodular functions: from discrete to continous domains. arXiv preprint arXiv:1511.00394, (2015)"},{"issue":"3","key":"1464_CR10","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0167-6377(02)00231-6","volume":"31","author":"A Beck","year":"2003","unstructured":"Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3), 167\u2013175 (2003)","journal-title":"Oper. Res. Lett."},{"key":"1464_CR11","volume-title":"Matrix Analysis, volume 169 of Graduate Texts in Mathematics","author":"R Bhatia","year":"1997","unstructured":"Bhatia, R.: Matrix Analysis, volume 169 of Graduate Texts in Mathematics. Springer, New York, NY (1997)"},{"key":"1464_CR12","unstructured":"Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.: Guarantees for greedy maximization of non-submodular functions with applications. In: Proceedings of International Conference on Machine Learning (ICML), (2017)"},{"key":"1464_CR13","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1016\/j.endm.2010.05.086","volume":"36","author":"M Bouhtou","year":"2010","unstructured":"Bouhtou, M., Gaubert, S., Sagnol, G.: Submodularity and randomized rounding techniques for optimal experimental design. Electron. Notes Discret. Math. 36, 679\u2013686 (2010)","journal-title":"Electron. Notes Discret. Math."},{"key":"1464_CR14","doi-asserted-by":"crossref","unstructured":"Boutsidis, C., Woodruff, D.P.: Optimal CUR matrix decompositions. In: Proceedings of Annual Symposium on the Theory of Computing (STOC), (2014)","DOI":"10.1145\/2591796.2591819"},{"key":"1464_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optim.","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optim. Cambridge University Press, Cambridge (2004)"},{"issue":"3","key":"1464_CR16","doi-asserted-by":"publisher","first-page":"1397","DOI":"10.1007\/s10589-010-9377-8","volume":"51","author":"M \u010cern\u1ef3","year":"2012","unstructured":"\u010cern\u1ef3, M., Hlad\u00edk, M.: Two complexity results on C-optimality in experimental design. Comput. Optim. Appl. 51(3), 1397\u20131408 (2012)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"1464_CR17","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1214\/ss\/1177009939","volume":"10","author":"K Chaloner","year":"1995","unstructured":"Chaloner, K., Verdinelli, I.: Bayesian experimental design: a review. Stat. Sci. 10(3), 273\u2013304 (1995)","journal-title":"Stat. Sci."},{"key":"1464_CR18","unstructured":"Chamon, L.F.O., Ribeiro, A.: Greedy sampling of graph signals. arXiv preprint arXiv:1704.01223, (2017)"},{"key":"1464_CR19","unstructured":"Chaudhuri, K., Kakade, S., Netrapalli, P., Sanghavi, S.: Convergence rates of active learning for maximum likelihood estimation. In: Proceedings of Advances in Neural Information Processing Systems (NIPS), (2015)"},{"issue":"17","key":"1464_CR20","doi-asserted-by":"publisher","first-page":"4609","DOI":"10.1109\/TSP.2015.2441042","volume":"63","author":"S Chen","year":"2015","unstructured":"Chen, S., Sandryhaila, A., Moura, J.M.F., Kova\u010devi\u0107, J.: Signal recovery on graphs: Variation minimization. IEEE Trans. Signal Process. 63(17), 4609\u20134624 (2015)","journal-title":"IEEE Trans. Signal Process."},{"key":"1464_CR21","unstructured":"Chen, S., Varma, R., Singh, A., Kova\u010devi\u0107, J.: Signal representations on graphs: Tools and applications. arXiv preprint arXiv:1512.05406, (2015)"},{"issue":"4","key":"1464_CR22","first-page":"539","volume":"2","author":"S Chen","year":"2016","unstructured":"Chen, S., Varma, R., Singh, A., Kova\u010devi\u0107, J.: Signal recovery on graphs: fundamental limits of sampling strategies. IEEE Trans. Signal Inf. Process. Over Netw. 2(4), 539\u2013554 (2016)","journal-title":"IEEE Trans. Signal Inf. Process. Over Netw."},{"issue":"47\u201349","key":"1464_CR23","doi-asserted-by":"publisher","first-page":"4801","DOI":"10.1016\/j.tcs.2009.06.018","volume":"410","author":"A \u00c7ivril","year":"2009","unstructured":"\u00c7ivril, A., Magdon-Ismail, M.: On selecting a maximum volume sub-matrix of a matrix and related problems. Theoret. Comput. Sci. 410(47\u201349), 4801\u20134811 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"1464_CR24","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/s10107-015-0946-6","volume":"158","author":"L Condat","year":"2015","unstructured":"Condat, L.: Fast projection onto the simplex and the L1-ball. Math. Program. 158, 575\u2013585 (2015)","journal-title":"Math. Program."},{"issue":"1","key":"1464_CR25","first-page":"853","volume":"19","author":"M Derezi\u0144ski","year":"2018","unstructured":"Derezi\u0144ski, M., Warmuth, M.K.: Reverse iterative volume sampling for linear regression. J. Mach. Learn. Res. 19(1), 853\u2013891 (2018)","journal-title":"J. Mach. Learn. Res."},{"key":"1464_CR26","unstructured":"Dhillon, P., Lu, Y., Foster, D.P., Ungar, L.: New subsampling algorithms for fast least squares regression. In: Proceedings of Advances in Neural Information Processing Systems (NIPS) (2013)"},{"issue":"12","key":"1464_CR27","first-page":"2153","volume":"6","author":"P Drineas","year":"2005","unstructured":"Drineas, P., Mahoney, M.W.: On the Nystr\u00f6m method for approximating a gram matrix for improved kernel-based learning. J. Mach. Learn. Res. 6(12), 2153\u20132175 (2005)","journal-title":"J. Mach. Learn. Res."},{"issue":"2","key":"1464_CR28","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1137\/07070471X","volume":"30","author":"P Drineas","year":"2008","unstructured":"Drineas, P., Mahoney, M.W., Muthukrishnan, S.: Relative-error CUR matrix decompositions. SIAM J. Matrix Anal. Appl. 30(2), 844\u2013881 (2008)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1464_CR29","doi-asserted-by":"crossref","unstructured":"Duchi, J., Shalev-Shwartz, S., Singer, Y., Chandra, T.: Efficient projections onto the L1-ball for learning in high dimensions. In: Proceedings of International Conference on Machine learning (ICML) (2008)","DOI":"10.1145\/1390156.1390191"},{"key":"1464_CR30","volume-title":"Theory of Optimal Experiments","author":"VV Fedorov","year":"1972","unstructured":"Fedorov, V.V.: Theory of Optimal Experiments. Elsevier, Amsterdam (1972)"},{"issue":"2","key":"1464_CR31","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1109\/TSP.2008.2007095","volume":"57","author":"S Joshi","year":"2009","unstructured":"Joshi, S., Boyd, S.: Sensor selection via convex optimization. IEEE Trans. Signal Process. 57(2), 451\u2013462 (2009)","journal-title":"IEEE Trans. Signal Process."},{"key":"1464_CR32","unstructured":"Li, C., Jegelka, S., Sra, S.: Polynomial time algorithms for dual volume sampling. In: Proceedings of Advances in Neural Information Processing Systems (NIPS) (2017)"},{"issue":"3","key":"1464_CR33","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0001-8708(73)90011-X","volume":"11","author":"EH Lieb","year":"1973","unstructured":"Lieb, E.H.: Convex trace functions and the wigner-yanase-dyson conjecture. Adv. Math. 11(3), 267\u2013288 (1973)","journal-title":"Adv. Math."},{"key":"1464_CR34","unstructured":"McMahan, H.B.: Follow-the-regularized-leader and mirror descent: Equivalence theorems and L1 regularization. In: Procedings of International Conference on Artificial Intelligence and Statistics (AISTATS), (2011)"},{"issue":"4","key":"1464_CR35","first-page":"669","volume":"43","author":"A Miller","year":"1994","unstructured":"Miller, A., Nguyen, N.-K.: A Fedorov exchange algorithm for d-optimal design. J. Roy. Stat. Soc.: Ser. C (Appl. Stat.) 43(4), 669\u2013677 (1994)","journal-title":"J. Roy. Stat. Soc.: Ser. C (Appl. Stat.)"},{"key":"1464_CR36","doi-asserted-by":"crossref","unstructured":"Nikolov, A.: Randomized rounding for the largest simplex problem. In: Proceedings of the annual ACM symposium on Theory of computing (STOC) (2015)","DOI":"10.1145\/2746539.2746628"},{"key":"1464_CR37","doi-asserted-by":"crossref","unstructured":"Nikolov, A., Singh, M.: Maximizing determinants under partition constraints. In: Proceedings of the Annual ACM Symposium on Theory of Computing (STOC) (2016)","DOI":"10.1145\/2897518.2897649"},{"key":"1464_CR38","doi-asserted-by":"crossref","unstructured":"Nikolov, A., Singh, M., Tantipongpipat, U.T.: Proportional volume sampling and approximation algorithms for a-optimal design. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2019)","DOI":"10.1137\/1.9781611975482.84"},{"key":"1464_CR39","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719109","volume-title":"Optimal Design of Experiments","author":"F Pukelsheim","year":"2006","unstructured":"Pukelsheim, F.: Optimal Design of Experiments. SIAM, Philadelphia (2006)"},{"key":"1464_CR40","unstructured":"Rakhlin, A.: Lecture notes on online learning. Draft (2009). http:\/\/www-stat.wharton.upenn.edu\/~rakhlin\/courses\/stat991\/papers\/lecture_notes.pdf"},{"key":"1464_CR41","first-page":"567","volume":"14","author":"S Shalev-Shwartz","year":"2013","unstructured":"Shalev-Shwartz, S., Zhang, T.: Stochastic dual coordinate ascent methods for regularized loss minimization. J. Mach. Learn. Res. 14, 567\u2013599 (2013)","journal-title":"J. Mach. Learn. Res."},{"key":"1464_CR42","doi-asserted-by":"crossref","unstructured":"Singh, M., Xie, W.: Approximate positive correlated distributions and approximation algorithms for d-optimal design. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (2017)","DOI":"10.1137\/1.9781611975031.145"},{"issue":"6","key":"1464_CR43","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1137\/080734029","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. SIAM J. Comput. 40(6), 1913\u20131926 (2011)","journal-title":"SIAM J. Comput."},{"key":"1464_CR44","doi-asserted-by":"crossref","unstructured":"Summa, M.D., Eisenbrand, F., Faenza, Y., Moldenhauer, C.: On largest volume simplices and sub-determinants. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2015)","DOI":"10.1137\/1.9781611973730.23"},{"key":"1464_CR45","volume-title":"Asymptotic Statistics","author":"AW Van der Vaart","year":"2000","unstructured":"Van der Vaart, A.W.: Asymptotic Statistics, vol. 3. Cambridge University Press, Cambridge (2000)"},{"issue":"1","key":"1464_CR46","first-page":"2729","volume":"14","author":"S Wang","year":"2013","unstructured":"Wang, S., Zhang, Z.: Improving CUR matrix decomposition and the Nystr\u00f6m approximation via adaptive sampling. J. Mach. Learn. Res. 14(1), 2729\u20132769 (2013)","journal-title":"J. Mach. Learn. Res."},{"issue":"156","key":"1464_CR47","first-page":"1","volume":"18","author":"Y Wang","year":"2018","unstructured":"Wang, Y., Singh, A.: Provably correct active sampling algorithms for matrix column subset selection with missing data. J. Mach. Learn. Res. 18(156), 1\u201342 (2018)","journal-title":"J. Mach. Learn. Res."},{"issue":"143","key":"1464_CR48","first-page":"1","volume":"18","author":"Y Wang","year":"2017","unstructured":"Wang, Y., Wei Adams, Y., Singh, A.: On computationally tractable selection of experiments in regression models. J. Mach. Learn. Res. 18(143), 1\u201341 (2017)","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"1464_CR49","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1080\/00949658208810560","volume":"15","author":"WJ Welch","year":"1982","unstructured":"Welch, W.J.: Algorithmic complexity: three np-hard problems in computational statistics. J. Stat. Comput. Simul. 15(1), 17\u201325 (1982)","journal-title":"J. Stat. Comput. Simul."},{"key":"1464_CR50","unstructured":"Zinkevich, M.: Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the International Conference on Machine Learning (ICML) (2003)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01464-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01464-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01464-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T09:50:21Z","timestamp":1613037021000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01464-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,10]]},"references-count":50,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["1464"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01464-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,10]]},"assertion":[{"value":"8 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}