| \n “Near-Optimal Regret Guarantee of CE Heuristic for Online Linear Programming<\/strong>“<\/strong><\/p>\n by<\/em><\/p>\nWenjia Wang<\/b>\nAssistant Professor, Data Science and Analysis Thrust at the Information Hub<\/b>\nHong Kong University of Science and Technology (Guangzhou)\n<\/td>\n<\/tr>\n Certainty equivalent (CE) is a classical heuristic building on the intuition of replacing uncertainties with their average values, and making accept\/reject decisions accordingly. Despite being the workhorse algorithm for online linear programming, the performance guarantee of CE measured by the additive regret against the prophet benchmark, remains largely unclear. Existing results typically rely on strong technical conditions called non-degeneracy conditions, which are not imposed on problem primitives, hard to intuit and very restrictive.<\/p>\nIn this work, we show the (near) optimality of certainty equivalent (CE) for a fairly general class of instances, specified only by natural and mild assumptions on problem primitives, in particular, boundedness and smoothness on the (conditional) distribution of the reward. For centain class of instances, we prove that CE achieves an $O((log T)^2)$ regret, which is near optimal (with an additional $log T$ factor). En route characterizing the regret scaling, we borrow techniques such as the peeling device from the empirical processes and statistical theory, and establish concentration analysis of the solution to an optimization problem with large-size i.i.d. input, which may be of independent theoretical interest.<\/td>\n<\/tr>\n by Dr Wenjia Wang<\/p>\n Assistant Professor<\/p>\n Data Science and Analysis Thrust at the Information Hub, Hong Kong University of Science and Technology (Guangzhou)<\/p>\n 26 September 2024<\/p>\n","protected":false},"author":59,"featured_media":23406,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"set","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[35],"tags":[40],"class_list":["post-23575","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-seminars","tag-professional"],"acf":[],"_links":{"self":[{"href":"https:\/\/cde.nus.edu.sg\/isem\/wp-json\/wp\/v2\/posts\/23575","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cde.nus.edu.sg\/isem\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/cde.nus.edu.sg\/isem\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/cde.nus.edu.sg\/isem\/wp-json\/wp\/v2\/users\/59"}],"replies":[{"embeddable":true,"href":"https:\/\/cde.nus.edu.sg\/isem\/wp-json\/wp\/v2\/comments?post=23575"}],"version-history":[{"count":3,"href":"https:\/\/cde.nus.edu.sg\/isem\/wp-json\/wp\/v2\/posts\/23575\/revisions"}],"predecessor-version":[{"id":23579,"href":"https:\/\/cde.nus.edu.sg\/isem\/wp-json\/wp\/v2\/posts\/23575\/revisions\/23579"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/cde.nus.edu.sg\/isem\/wp-json\/wp\/v2\/media\/23406"}],"wp:attachment":[{"href":"https:\/\/cde.nus.edu.sg\/isem\/wp-json\/wp\/v2\/media?parent=23575"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/cde.nus.edu.sg\/isem\/wp-json\/wp\/v2\/categories?post=23575"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/cde.nus.edu.sg\/isem\/wp-json\/wp\/v2\/tags?post=23575"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}} |