{"id":1180662,"date":"2026-07-21T00:00:00","date_gmt":"2026-07-21T07:00:00","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/the-price-of-hidden-curvature-an-widetilde%cf%89-d5-4-sqrtt-lower-bound-for-bandit-convex-optimization\/"},"modified":"2026-08-03T08:15:32","modified_gmt":"2026-08-03T15:15:32","slug":"the-price-of-hidden-curvature-an-widetilde%cf%89-d5-4-sqrtt-lower-bound-for-bandit-convex-optimization","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/the-price-of-hidden-curvature-an-widetilde%cf%89-d5-4-sqrtt-lower-bound-for-bandit-convex-optimization\/","title":{"rendered":"The Price of Hidden Curvature: An\u00a0\u03a9\u02dc(d5\/4T\u2212\u2212\u221a)\u00a0Lower Bound for Bandit Convex Optimization"},"content":{"rendered":"\n\n\n<p class=\"wp-block-paragraph\">We establish a <math><semantics><mrow><mtext>widetildeOmega(d^{5\/4}sqrt T)<\/mtext><\/mrow><annotation encoding=\"application\/x-tex\">widetildeOmega(d^{5\/4}sqrt T)<\/annotation><\/semantics><\/math> lower bound on the minimax expected regret of stochastic bandit convex optimization of <math><mn>1<\/mn><\/math>-Lipschitz functions on the Euclidean ball. This presents the first nontrivial regret lower bound that grows faster than <math><mrow><mi>d<\/mi><msqrt><mi>T<\/mi><\/msqrt><\/mrow><\/math> for this problem, establishing that stochastic bandit convex optimization is fundamentally harder than linear bandits. The hard class of convex functions we construct takes the following form in dimension <math><mrow><mn>2<\/mn><mi>d<\/mi><\/mrow><\/math>: for an action <math><mrow><mi>a<\/mi><mo>=<\/mo><mo stretchy=\"false\">(<\/mo><msup><mi>a<\/mi><mn>1<\/mn><\/msup><mo>,<\/mo><msup><mi>a<\/mi><mn>2<\/mn><\/msup><mo stretchy=\"false\">)<\/mo><mo>\u2208<\/mo><msubsup><mi>\ud835\udd39<\/mi><mn>2<\/mn><mrow><mrow><mn>2<\/mn><mi>d<\/mi><\/mrow><\/mrow><\/msubsup><\/mrow><\/math>, each function is the scaled soft maximum of a&#8221;tube&#8221;, <math><semantics><mrow><mtext>r^{-1} \\| W^star a^1 &#8211; frac{r}{8varepsilon} a^2 \\|_2<\/mtext><\/mrow><annotation encoding=\"application\/x-tex\">r^{-1} \\| W^star a^1 &#8211; frac{r}{8varepsilon} a^2 \\|_2<\/annotation><\/semantics><\/math> (hyperparameterized by <math><mrow><mi>\u03b5<\/mi><mo>,<\/mo><mi>r<\/mi><\/mrow><\/math>), and a squared distance function, <math><semantics><mrow><mtext>frac12 \\| a^1 &#8211; u^star \\|_2^2 &#8211; frac12 \\| u^star \\|_2^2<\/mtext><\/mrow><annotation encoding=\"application\/x-tex\">frac12 \\| a^1 &#8211; u^star \\|_2^2 &#8211; frac12 \\| u^star \\|_2^2<\/annotation><\/semantics><\/math>. Here, <math><mrow><msup><mi>W<\/mi><\/msup><mo>\u2208<\/mo><msup><mi>\u211d<\/mi><mrow><mrow><mi>d<\/mi><mo>\u00d7<\/mo><mi>d<\/mi><\/mrow><\/mrow><\/msup><\/mrow><\/math> is an unknown linear transformation, and <math><mrow><msup><mi>u<\/mi><\/msup><mo>\u2208<\/mo><msup><mi>\u211d<\/mi><mi>d<\/mi><\/msup><\/mrow><\/math> is an unknown vector which must be learned to minimize the function. Observations are informative about <math><mrow><msup><mi>u<\/mi><\/msup><\/mrow><\/math> only when the learner&#8217;s action lies near the tube determined by <math><mrow><msup><mi>W<\/mi><\/msup><\/mrow><\/math>, satisfying <math><mrow><msup><mi>a<\/mi><mn>2<\/mn><\/msup><mo>\u2248<\/mo><mfrac><mrow><mrow><mn>8<\/mn><mi>\u03b5<\/mi><\/mrow><\/mrow><mi>r<\/mi><\/mfrac><msup><mi>W<\/mi><\/msup><msup><mi>a<\/mi><mn>1<\/mn><\/msup><\/mrow><\/math>: thus the learner must either find this tube without knowing <math><mrow><msup><mi>W<\/mi><\/msup><\/mrow><\/math>, or spend observations learning useful directions of <math><mrow><msup><mi>W<\/mi><\/msup><\/mrow><\/math>. Formally, our regret analysis exploits this tradeoff by bounding the posterior spread of Fisher information matrices obtained under an adaptive sequence of actions. Together, these ingredients give a sample complexity lower bound of <math><semantics><mrow><mtext>widetilde{Omega}(d^{5\/2}\/varepsilon^2)<\/mtext><\/mrow><annotation encoding=\"application\/x-tex\">widetilde{Omega}(d^{5\/2}\/varepsilon^2)<\/annotation><\/semantics><\/math> to find an <math><mi>\u03b5<\/mi><\/math>-optimal action, which translates to an <math><semantics><mrow><mtext>widetilde{Omega} (d^{5\/4} sqrt{T})<\/mtext><\/mrow><annotation encoding=\"application\/x-tex\">widetilde{Omega} (d^{5\/4} sqrt{T})<\/annotation><\/semantics><\/math> regret lower bound. We also extend this lower bound to the unconstrained setting where the action space is <math><mrow><msup><mi>\u211d<\/mi><mi>d<\/mi><\/msup><\/mrow><\/math>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We establish a widetildeOmega(d^{5\/4}sqrt T)widetildeOmega(d^{5\/4}sqrt T) lower bound on the minimax expected regret of stochastic bandit convex optimization of 1-Lipschitz functions on the Euclidean ball. This presents the first nontrivial regret lower bound that grows faster than dT for this problem, establishing that stochastic bandit convex optimization is fundamentally harder than linear bandits. The hard [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":[{"type":"text","value":"Nived Rajaraman","user_id":0}],"msr_publishername":"","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"","msr_editors":"","msr_how_published":"arXiv","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"","msr_doi":"","msr_arxiv_id":"2607.18652","msr_mag_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_release_tracker_id":"","msr_highlight_type":"","msr_date_display_format":"","msr_main_download_label":"","msr_external_link_label":"","msr_doi_label":"","msr_published_date":"2026-07-21","msr_startdate":"","msr_presentation_date":"","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_year":2026,"msr_month":7,"msr_day":21,"msr_microsoftintellectualproperty":false,"msr_pub_id":"b563596689758156ad34759395b507386bf64fe8","msr_publication_uploader":[{"type":"url","title":"https:\/\/arxiv.org\/abs\/2607.18652","label_id":243109,"id":false,"viewUrl":false}],"msr_related_uploader":[],"msr_original_fields_of_study":[],"msr_s2_paper_id":"","msr_s2_pdf_url":"","msr_citation_count_updated":"","msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[{"provider":"s2","id":"b563596689758156ad34759395b507386bf64fe8"},{"provider":"arxiv","id":"2607.18652"},{"provider":"corpusid","id":"290466658"}],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13556,13546],"msr-publication-type":[270373],"msr-publisher":[],"msr-publication-cta":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[246691,265497,246907],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-1180662","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-artificial-intelligence","msr-research-area-computational-sciences-mathematics","msr-locale-en_us","msr-field-of-study-computer-science","msr-field-of-study-machine-learning-296","msr-field-of-study-mathematics"],"msr_publishername":"","msr_edition":"","msr_affiliation":"","msr_published_date":"2026-07-21","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"arXiv","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":0,"msr_main_download":"","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"url","title":"https:\/\/arxiv.org\/abs\/2607.18652","label_id":243109,"id":false,"viewUrl":false}],"msr_related_uploader":[],"msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"2607.18652","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[],"msr-author-ordering":[{"type":"text","value":"Nived Rajaraman","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[199571],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"misc","related_content":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1180662","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":4,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1180662\/revisions"}],"predecessor-version":[{"id":1180695,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1180662\/revisions\/1180695"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=1180662"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=1180662"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=1180662"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=1180662"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=1180662"},{"taxonomy":"msr-publication-cta","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-cta?post=1180662"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=1180662"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=1180662"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=1180662"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=1180662"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=1180662"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=1180662"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=1180662"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=1180662"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}