{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:04:57Z","timestamp":1760123097958,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council Starting Grant","award":["803084\/5"],"award-info":[{"award-number":["803084\/5"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["715\/16"],"award-info":[{"award-number":["715\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p>\n            We consider the adversarial convex bandit problem and we build the first poly(\n            <jats:italic>T<\/jats:italic>\n            )-time algorithm with poly(\n            <jats:italic>n<\/jats:italic>\n            ) \u221a\n            <jats:italic>T<\/jats:italic>\n            -regret for this problem. To do so, we introduce three new ideas in the derivative-free optimization literature: (i) kernel methods, (ii) a generalization of Bernoulli convolutions, and (iii) a new annealing schedule for exponential weights (with increasing learning rate). The basic version of our algorithm achieves  \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>9.5<\/jats:sup>\n            \u221a\n            <jats:italic>T<\/jats:italic>\n            )-regret, and we show that a simple variant of this algorithm can be run in poly(\n            <jats:italic>n<\/jats:italic>\n            log (\n            <jats:italic>T<\/jats:italic>\n            ))-time per step (for polytopes with polynomially many constraints) at the cost of an additional poly(\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:italic>T<\/jats:italic>\n            <jats:sup>o(1)<\/jats:sup>\n            factor in the regret. These results improve upon the \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>11<\/jats:sup>\n            \u221a\n            <jats:italic>T<\/jats:italic>\n            -regret and exp (poly(\n            <jats:italic>T<\/jats:italic>\n            ))-time result of the first two authors and the log (\n            <jats:italic>T<\/jats:italic>\n            )\n            <jats:sup>\n              poly(\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            \u221a\n            <jats:italic>T<\/jats:italic>\n            -regret and log(\n            <jats:italic>T<\/jats:italic>\n            )\n            <jats:sup>\n              poly(\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            -time result of Hazan and Li. Furthermore, we conjecture that another variant of the algorithm could achieve \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1.5<\/jats:sup>\n            \u221a\n            <jats:italic>T<\/jats:italic>\n            )-regret, and moreover that this regret is unimprovable (the current best lower bound being \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            \u221a\n            <jats:italic>T<\/jats:italic>\n            ) and it is achieved with linear functions). For the simpler situation of zeroth order stochastic convex optimization this corresponds to the conjecture that the optimal query complexity is of order\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            \/ \u025b\n            <jats:sup>2<\/jats:sup>\n            .\n          <\/jats:p>","DOI":"10.1145\/3453721","type":"journal-article","created":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T19:11:05Z","timestamp":1625080265000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Kernel-based Methods for Bandit Convex Optimization"],"prefix":"10.1145","volume":"68","author":[{"given":"S\u00e9bastien","family":"Bubeck","sequence":"first","affiliation":[{"name":"Microsoft Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronen","family":"Eldan","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,30]]},"reference":[{"volume-title":"Proceedings of the 21st Conference on Learning Theory (COLT\u201908)","author":"Abernethy J.","key":"e_1_2_1_1_1","unstructured":"J. Abernethy , E. Hazan , and A. Rakhlin . 2008. Competing in the dark: An efficient algorithm for bandit linear optimization . In Proceedings of the 21st Conference on Learning Theory (COLT\u201908) . J. Abernethy, E. Hazan, and A. Rakhlin. 2008. Competing in the dark: An efficient algorithm for bandit linear optimization. In Proceedings of the 21st Conference on Learning Theory (COLT\u201908)."},{"volume-title":"Proceedings of the 23rd Conference on Learning Theory (COLT\u201910)","author":"Agarwal A.","key":"e_1_2_1_2_1","unstructured":"A. Agarwal , O. Dekel , and L. Xiao . 2010. Optimal algorithms for online convex optimization with multi-point bandit feedback . In Proceedings of the 23rd Conference on Learning Theory (COLT\u201910) . A. Agarwal, O. Dekel, and L. Xiao. 2010. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Proceedings of the 23rd Conference on Learning Theory (COLT\u201910)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2986459.2986575"},{"volume-title":"Proceedings of the 29th Conference on Learning Theory (COLT\u201916)","author":"Bach F.","key":"e_1_2_1_4_1","unstructured":"F. Bach and V. Perchet . 2016. Highly-smooth zero-th order online optimization . In Proceedings of the 29th Conference on Learning Theory (COLT\u201916) . F. Bach and V. Perchet. 2016. Highly-smooth zero-th order online optimization. In Proceedings of the 29th Conference on Learning Theory (COLT\u201916)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-03-11912-2"},{"volume-title":"Proceedings of the 28th Conference on Learning Theory (COLT\u201915)","author":"Belloni A.","key":"e_1_2_1_6_1","unstructured":"A. Belloni , T. Liang , H. Narayanan , and A. Rakhlin . 2015. Escaping the local minima via simulated annealing: Optimization of approximately convex functions . In Proceedings of the 28th Conference on Learning Theory (COLT\u201915) . A. Belloni, T. Liang, H. Narayanan, and A. Rakhlin. 2015. Escaping the local minima via simulated annealing: Optimization of approximately convex functions. In Proceedings of the 28th Conference on Learning Theory (COLT\u201915)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000024"},{"volume-title":"Proceedings of the 25th Conference on Learning Theory (COLT\u201912)","author":"Bubeck S.","key":"e_1_2_1_8_1","unstructured":"S. Bubeck , N. Cesa-Bianchi , and S. M. Kakade . 2012. Towards minimax policies for online linear optimization with bandit feedback . In Proceedings of the 25th Conference on Learning Theory (COLT\u201912) . S. Bubeck, N. Cesa-Bianchi, and S. M. Kakade. 2012. Towards minimax policies for online linear optimization with bandit feedback. In Proceedings of the 25th Conference on Learning Theory (COLT\u201912)."},{"volume-title":"Proceedings of the 28th Conference on Learning Theory (COLT\u201915)","author":"Bubeck S.","key":"e_1_2_1_9_1","unstructured":"S. Bubeck , O. Dekel , T. Koren , and Y. Peres . 2015. Bandit convex optimization: regret in one dimension . In Proceedings of the 28th Conference on Learning Theory (COLT\u201915) . S. Bubeck, O. Dekel, T. Koren, and Y. Peres. 2015. Bandit convex optimization: regret in one dimension. In Proceedings of the 28th Conference on Learning Theory (COLT\u201915)."},{"volume-title":"Proceedings of the 29th Conference on Learning Theory (COLT\u201916)","author":"Bubeck S.","key":"e_1_2_1_10_1","unstructured":"S. Bubeck and R. Eldan . 2016. Multi-scale exploration of convex functions and bandit convex optimization . In Proceedings of the 29th Conference on Learning Theory (COLT\u201916) . S. Bubeck and R. Eldan. 2016. Multi-scale exploration of convex functions and bandit convex optimization. In Proceedings of the 29th Conference on Learning Theory (COLT\u201916)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1508119"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2981562.2981606"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2969442.2969567"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371641"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070486"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2968826.2968914"},{"key":"e_1_2_1_17_1","unstructured":"E. Hazan and Y. Li. 2016. An optimal algorithm for bandit convex optimization. arXiv preprint arXiv:1603.04350 (2016).  E. Hazan and Y. Li. 2016. An optimal algorithm for bandit convex optimization. arXiv preprint arXiv:1603.04350 (2016)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-004-0344-0"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2976040.2976128"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.23"},{"key":"e_1_2_1_21_1","volume-title":"Path finding i: Solving linear programs with  linear system solves. arXiv preprint arXiv:1312.6677","author":"Lee Yin Tat","year":"2013","unstructured":"Yin Tat Lee and Aaron Sidford . 2013. Path finding i: Solving linear programs with linear system solves. arXiv preprint arXiv:1312.6677 ( 2013 ). Yin Tat Lee and Aaron Sidford. 2013. Path finding i: Solving linear programs with linear system solves. arXiv preprint arXiv:1312.6677 (2013)."},{"key":"e_1_2_1_22_1","first-page":"1244","article-title":"On an algorithm for the minimization of convex functions","volume":"160","author":"Levin A.","year":"1965","unstructured":"A. Levin . 1965 . On an algorithm for the minimization of convex functions . In Soviet Math. Dok , Vol. 160. 1244 \u2013 1247 . A. Levin. 1965. On an algorithm for the minimization of convex functions. In Soviet Math. Dok, Vol. 160. 1244\u20131247.","journal-title":"Soviet Math. Dok"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.28"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1234700.1234701"},{"key":"e_1_2_1_25_1","volume-title":"Lecture Notes in Math.","volume":"1376","author":"Milman V. D.","unstructured":"V. D. Milman and A. Pajor . 1989. Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed -dimensional space. In Geometric Aspects of Functional Analysis (1987\u201388) . Lecture Notes in Math. , Vol. 1376 . Springer, Berlin, 64\u2013104. V. D. Milman and A. Pajor. 1989. Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed -dimensional space. In Geometric Aspects of Functional Analysis (1987\u201388). Lecture Notes in Math., Vol. 1376. Springer, Berlin, 64\u2013104."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3020948.3021032"},{"key":"e_1_2_1_27_1","unstructured":"A. Nemirovski and D. Yudin. 1983. Problem Complexity and Method Efficiency in Optimization. Wiley Interscience.  A. Nemirovski and D. Yudin. 1983. Problem Complexity and Method Efficiency in Optimization. Wiley Interscience."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/321281.321291"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Y. Peres W. Schlag and B. Solomyak. 2000. Sixty years of Bernoulli convolutions. In Fractal Geometry and Stochastics II. Springer 39\u201365.  Y. Peres W. Schlag and B. Solomyak. 2000. Sixty years of Bernoulli convolutions. In Fractal Geometry and Stochastics II. Springer 39\u201365.","DOI":"10.1007\/978-3-0348-8380-1_2"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02312467"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/3.3.175"},{"volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTAT\u201911)","author":"Saha A.","key":"e_1_2_1_32_1","unstructured":"A. Saha and A. Tewari . 2011. Improved regret guarantees for online smooth convex optimization with bandit feedback . In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTAT\u201911) . 636\u2013642. A. Saha and A. Tewari. 2011. Improved regret guarantees for online smooth convex optimization with bandit feedback. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTAT\u201911). 636\u2013642."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 26th Conference on Learning Theory (COLT\u201913)","author":"Shamir O.","year":"2013","unstructured":"O. Shamir . 2013 . On the complexity of bandit and derivative-free stochastic convex optimization . In Proceedings of the 26th Conference on Learning Theory (COLT\u201913) . O. Shamir. 2013. On the complexity of bandit and derivative-free stochastic convex optimization. In Proceedings of the 26th Conference on Learning Theory (COLT\u201913)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2969442.2969597"},{"volume-title":"Introduction to the non-asymptotic analysis of random matrices","author":"Vershynin R.","key":"e_1_2_1_35_1","unstructured":"R. Vershynin . 2012. Introduction to the non-asymptotic analysis of random matrices . In Compressed Sensing, Yonina C. Eldar and Gitta Kutyniok (Eds.). Cambridge University Press , 210\u2013268. R. Vershynin. 2012. Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing, Yonina C. Eldar and Gitta Kutyniok (Eds.). Cambridge University Press, 210\u2013268."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3157096.3157353"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453721","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3453721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:47Z","timestamp":1750195727000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1145\/3453721"],"URL":"https:\/\/doi.org\/10.1145\/3453721","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2021,6,30]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}