{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T21:57:46Z","timestamp":1648677466585},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,9,12]],"date-time":"2014-09-12T00:00:00Z","timestamp":1410480000000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00224-014-9570-8","type":"journal-article","created":{"date-parts":[[2014,9,11]],"date-time":"2014-09-11T01:33:05Z","timestamp":1410399185000},"page":"191-222","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Two Continuum Armed Bandit Problems in High Dimensions"],"prefix":"10.1007","volume":"58","author":[{"given":"Hemant","family":"Tyagi","sequence":"first","affiliation":[]},{"given":"Sebastian U.","family":"Stich","sequence":"additional","affiliation":[]},{"given":"Bernd","family":"G\u00e4rtner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,9,12]]},"reference":[{"key":"9570_CR1","unstructured":"Abbasi-yadkori, Y., Pal, D., Szepesvari, C.: Online-to-confidence-set conversions and application to sparse stochastic bandits. In: Proceedings of AIStats (2012)"},{"key":"9570_CR2","unstructured":"Abernethy, J., Hazan, E., Rakhlin, A.: Competing in the dark: An efficient algorithm for bandit linear optimization. In: Proceedings of the 21st Annual Conference on Learning Theory (COLT) (2008)"},{"key":"9570_CR3","doi-asserted-by":"crossref","first-page":"1926","DOI":"10.1137\/S0363012992237273","volume":"33","author":"R Agrawal","year":"1995","unstructured":"Agrawal, R.: The continuum-armed bandit problem. SIAM J. Control Optim. 33, 1926\u20131951 (1995)","journal-title":"SIAM J. Control Optim."},{"key":"9570_CR4","first-page":"2635","volume":"11","author":"JY Audibert","year":"2010","unstructured":"Audibert, J.Y., Bubeck, S.: Regret bounds and minimax policies under partial monitoring. J. Mach. Learn. Res. 11, 2635\u20132686 (2010)","journal-title":"J. Mach. Learn. Res."},{"issue":"2-3","key":"9570_CR5","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1023\/A:1013689704352","volume":"47","author":"P Auer","year":"2002","unstructured":"Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-time analysis of the multiarmed bandit problem. Mach. Learn. 47 (2-3), 235\u2013256 (2002)","journal-title":"Mach. Learn."},{"key":"9570_CR6","doi-asserted-by":"crossref","unstructured":"Auer, P., Cesa-Bianchi, N., Freund, Y., Schapire, R.: Gambling in a rigged casino: The adversarial multi-armed bandit problem. In: Proceedings of 36th Annual Symposium on Foundations of Computer Science, 1995, pp. 322\u2013331 (1995)","DOI":"10.1109\/SFCS.1995.492488"},{"issue":"1","key":"9570_CR7","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1137\/S0097539701398375","volume":"32","author":"P Auer","year":"2003","unstructured":"Auer, P., Cesa-Bianchi, N., Freund, Y., Schapire, R.: The nonstochastic multiarmed bandit problem. SIAM J. Comput. 32 (1), 48\u201377 (2003)","journal-title":"SIAM J. Comput."},{"key":"9570_CR8","doi-asserted-by":"crossref","unstructured":"Auer, P., Ortner, R., Szepesvari, C.: Improved rates for the stochastic continuum-armed bandit problem. In: Proceedings of 20th Conference on Learning Theory (COLT), pp. 454\u2013468 (2007)","DOI":"10.1007\/978-3-540-72927-3_33"},{"key":"9570_CR9","doi-asserted-by":"crossref","unstructured":"Bansal, N., Blum, A., Chawla, S., Meyerson, A.: Online oblivious routing. In: Proceedings of ACM Symposium in Parallelism in Algorithms and Architectures, pp. 44\u201349 (2003)","DOI":"10.1145\/777412.777420"},{"key":"9570_CR10","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1162\/089976603321780317","volume":"15","author":"M Belkin","year":"2003","unstructured":"Belkin, M., Niyogi, P.: Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput. 15, 1373\u20131396 (2003)","journal-title":"Neural Comput."},{"key":"9570_CR11","unstructured":"Blum, A., Kumar, V., Rudra, A., Wu, F.: Online learning in online auctions. In: Proceedings of 14th Symp. on Discrete Alg., pp. 202\u2013204 (2003)"},{"key":"9570_CR12","first-page":"1587","volume":"12","author":"S Bubeck","year":"2011","unstructured":"Bubeck, S., Munos, R., Stoltz, G., Szepesvari, C.: X-armed bandits. J. Mach. Learn. Res. (JMLR) 12, 1587\u20131627 (2011)","journal-title":"J. Mach. Learn. Res. (JMLR)"},{"key":"9570_CR13","doi-asserted-by":"crossref","unstructured":"Bubeck, S., Stoltz, G., Yu, J.: Lipschitz bandits without the Lipschitz constant. In: Proceedings of the 22nd International Conference on Algorithmic Learning Theory (ALT), pp. 144\u2013158 (2011)","DOI":"10.1007\/978-3-642-24412-4_14"},{"key":"9570_CR14","unstructured":"Cand\u00e8s, E., Plan, Y.: Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements. CoRR abs\/1001.0339 (2010)"},{"key":"9570_CR15","unstructured":"Carpentier, A., Munos, R.: Bandit theory meets compressed sensing for high dimensional stochastic linear bandit. In: Proceedings of AIStats, pp. 190\u2013198 (2012)"},{"key":"9570_CR16","unstructured":"Chen, B., Castro, R., Krause, A.: Joint optimization and variable selection of high-dimensional gaussian processes. In: Proceedings International Conference on Machine Learning (ICML) (2012)"},{"key":"9570_CR17","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.acha.2006.04.004","volume":"21","author":"R Coifman","year":"2006","unstructured":"Coifman, R., Maggioni, M.: Diffusion wavelets. Appl. Comput. Harmon. Anal. 21, 53\u201394 (2006)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9570_CR18","doi-asserted-by":"crossref","first-page":"1243","DOI":"10.1109\/TAC.2009.2019797","volume":"54","author":"E Cope","year":"2009","unstructured":"Cope, E.: Regret and convergence bounds for a class of continuum-armed bandit problems. IEEE Trans. Autom. Control 54, 1243\u20131253 (2009)","journal-title":"IEEE Trans. Autom. Control"},{"key":"9570_CR19","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s00365-010-9105-8","volume":"33","author":"R DeVore","year":"2011","unstructured":"DeVore, R., Petrova, G., Wojtaszczyk, P.: Approximation of functions of few variables in high dimensions. Constr. Approx 33, 125\u2013143 (2011)","journal-title":"Constr. Approx"},{"key":"9570_CR20","unstructured":"Djolonga, J., Krause, A., Cevher, V.: High dimensional gaussian process bandits. In: To Appear in Neural Information Processing Systems (NIPS) (2013)"},{"key":"9570_CR21","unstructured":"Flaxman, A., Kalai, A., McMahan, H.: Online convex optimization in the bandit setting: gradient descent without a gradient. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 385\u2013394 (2005)"},{"issue":"2","key":"9570_CR22","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s10208-012-9115-y","volume":"12","author":"M Fornasier","year":"2012","unstructured":"Fornasier, M., Schnass, K., Vybiral, J.: Learning functions of few arbitrary linear parameters in high dimensions. Found. Comput. Math. 12 (2), 229\u2013262 (2012)","journal-title":"Found. Comput. Math."},{"key":"9570_CR23","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1137\/0605009","volume":"5","author":"M Fredman","year":"1984","unstructured":"Fredman, M., Koml\u00f3s, J.: On the size of separating systems and families of perfect hash functions. SIAM. J. Algebr. Discret. Methods 5, 61\u201368 (1984)","journal-title":"SIAM. J. Algebr. Discret. Methods"},{"issue":"3","key":"9570_CR24","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M Fredman","year":"1984","unstructured":"Fredman, M., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with 0(1) worst case access time. J. ACM 31 (3), 538\u2013544 (1984)","journal-title":"J. ACM"},{"key":"9570_CR25","doi-asserted-by":"crossref","first-page":"2367","DOI":"10.1214\/009053606000000768","volume":"34","author":"E Greenshtein","year":"2006","unstructured":"Greenshtein, E.: Best subset selection, persistence in high dimensional statistical learning and optimization under \u2113 1 constraint. Ann. Stat. 34, 2367\u20132386 (2006)","journal-title":"Ann. Stat."},{"key":"9570_CR26","unstructured":"Kleinberg, R.: Nearly tight bounds for the continuum-armed bandit problem. In: 18th Advances in Neural Information Processing Systems (2004)"},{"key":"9570_CR27","unstructured":"Kleinberg, R.: Online decision problems with large strategy sets. Ph.D. thesis. MIT, Boston (2005)"},{"key":"9570_CR28","doi-asserted-by":"crossref","unstructured":"Kleinberg, R., Leighton, T.: The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In: Proceedings of Foundations of Computer Science, 2003., pp. 594\u2013605 (2003)","DOI":"10.1109\/SFCS.2003.1238232"},{"key":"9570_CR29","doi-asserted-by":"crossref","unstructured":"Kleinberg, R., Slivkins, A., Upfal, E.: Multi-armed bandits in metric spaces. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC \u201908, pp. 681\u2013690 (2008)","DOI":"10.1145\/1374376.1374475"},{"issue":"4","key":"9570_CR30","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1137\/0607062","volume":"7","author":"J K\u00f6rner","year":"1986","unstructured":"K\u00f6rner, J.: Fredmankoml\u00f3s bounds and information theory. SIAM J. Algebraic Discret. Methods 7 (4), 560\u2013570 (1986)","journal-title":"SIAM J. Algebraic Discret. Methods"},{"issue":"5","key":"9570_CR31","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1214\/aos\/1015957395","volume":"28","author":"B Laurent","year":"2000","unstructured":"Laurent, B., Massart, P.: Adaptive estimation of a quadratic functional by model selection. Ann. Stat. 28 (5), 1302\u20131338 (2000)","journal-title":"Ann. Stat."},{"key":"9570_CR32","doi-asserted-by":"crossref","unstructured":"Li, Q., Racine, J.: Nonparametric econometrics: Theory and practice (2007)","DOI":"10.1561\/0800000009"},{"key":"9570_CR33","doi-asserted-by":"crossref","unstructured":"McMahan, B., Blum, A.: Online geometric optimization in the bandit setting against an adaptive adversary. In: Proceedings of the 17th Annual Conference on Learning Theory (COLT), pp. 109\u2013123 (2004)","DOI":"10.1007\/978-3-540-27819-1_8"},{"key":"9570_CR34","doi-asserted-by":"crossref","unstructured":"Mossel, E., O\u2019Donnell, R., Servedio, R.: Learning juntas. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC, pp. 206\u2013212. ACM (2003)","DOI":"10.1145\/780542.780574"},{"key":"9570_CR35","doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pp. 182\u2013191 (1995)","DOI":"10.1109\/SFCS.1995.492475"},{"key":"9570_CR36","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1017\/S0963548300001280","volume":"3","author":"A Nilli","year":"1994","unstructured":"Nilli, A.: Perfect hashing and probability. Comb. Probab. Comput. 3, 407\u2013409 (1994)","journal-title":"Comb. Probab. Comput."},{"key":"9570_CR37","doi-asserted-by":"crossref","first-page":"1111","DOI":"10.1109\/18.57210","volume":"36","author":"A Orlitsky","year":"1990","unstructured":"Orlitsky, A.: Worst-case interactive communication i: Two messages are almost optimal. IEEE Trans. Inf. Theory 36, 1111\u20131126 (1990)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9570_CR38","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/070697835","volume":"52","author":"B Recht","year":"2010","unstructured":"Recht, B., Fazel, M., Parrilo, P.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52, 471\u2013501 (2010)","journal-title":"SIAM Rev."},{"issue":"4","key":"9570_CR39","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/s10208-011-9099-z","volume":"12","author":"J Tropp","year":"2012","unstructured":"Tropp, J.: User-friendly tail bounds for sums of random matrices. Found. Comput. Math. 12 (4), 389\u2013434 (2012)","journal-title":"Found. Comput. Math."},{"key":"9570_CR40","unstructured":"Tyagi, H., Cevher, V.: Active learning of multi-index function models. In: Advances in Neural Information Processing Systems, vol. 25, pp. 1475\u20131483 (2012)"},{"key":"9570_CR41","doi-asserted-by":"crossref","unstructured":"Tyagi, H., Cevher, V.: Learning non-parametric basis independent models from point queries via low-rank methods. Appl. Comput. Harmonic Anal. (2014)","DOI":"10.1016\/j.acha.2014.01.002"},{"key":"9570_CR42","doi-asserted-by":"crossref","unstructured":"Tyagi, H., G\u00e4rtner, B.: Continuum armed bandit problem of few variables in high dimensions. CoRR abs\/1304.5793 (2013)","DOI":"10.1007\/978-3-319-08001-7_10"},{"key":"9570_CR43","unstructured":"Wang, Z., Zoghi, M., Hutter, F., Matheson, D., de Freitas, N.: Bayesian optimization in high dimensions via random embeddings. In: Proc. IJCAI (2013)"},{"key":"9570_CR44","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01932678","volume":"12","author":"P Wedin","year":"1972","unstructured":"Wedin, P.: Perturbation bounds in connection with singular value decomposition. BIT 12, 99\u2013111 (1972)","journal-title":"BIT"},{"key":"9570_CR45","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/BF01456804","volume":"71","author":"H Weyl","year":"1912","unstructured":"Weyl, H.: Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung). Mathematische Annalen 71, 441\u2013479 (1912)","journal-title":"Mathematische Annalen"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9570-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9570-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9570-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T17:58:25Z","timestamp":1565805505000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9570-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,12]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9570"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9570-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,12]]}}}