{"id":519,"date":"2024-12-12T07:03:56","date_gmt":"2024-12-12T07:03:56","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2024\/12\/12\/2412-08060\/"},"modified":"2024-12-12T07:03:56","modified_gmt":"2024-12-12T07:03:56","slug":"2412-08060","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2024\/12\/12\/2412-08060\/","title":{"rendered":"An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints"},"content":{"rendered":"

An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

arXiv:2412.08060v1 Announce Type: new
\nAbstract: We study Online Convex Optimization (OCO) with adversarial constraints, where an online algorithm must make repeated decisions to minimize both convex loss functions and cumulative constraint violations. We focus on a setting where the algorithm has access to predictions of the loss and constraint functions. Our results show that we can improve the current best bounds of $ O(sqrt{T}) $ regret and $ tilde{O}(sqrt{T}) $ cumulative constraint violations to $ O(sqrt{E_T(f)}) $ and $ tilde{O}(sqrt{E_T(g)}) $, respectively, where $ E_T(f) $ and $ E_T(g) $ represent the cumulative prediction errors of the loss and constraint functions. In the worst case, where $ E_T(f) = O(T) $ and $ E_T(g) = O(T) $ (assuming bounded loss and constraint functions), our rates match the prior $ O(sqrt{T}) $ results. However, when the loss and constraint predictions are accurate, our approach yields significantly smaller regret and cumulative constraint violations. Notably, if the constraint function remains constant over time, we achieve $ tilde{O}(1) $ cumulative constraint violation, aligning with prior results.<\/div>\n

\t

\n
<\/BR>
\n Jordan Lekeufack, Michael I. Jordan
\n \t

\n
<\/BR>
\nGo to original source<\/a>
\n \t

\n
<\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"

An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints arXiv:2412.08060v1 Announce Type: new Abstract: We study Online Convex Optimization (OCO) with adversarial constraints, where an online algorithm must make repeated decisions to minimize both convex loss functions and cumulative constraint violations. We focus on a setting where the algorithm has access to predictions of […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,113,376,112],"tags":[635,637,636],"class_list":["post-519","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-lg","category-math-oc","category-stat-ml","tag-constraint","tag-cumulative","tag-loss"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/519"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=519"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/519\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=519"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=519"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=519"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}