{"id":9581,"date":"2026-01-08T07:02:29","date_gmt":"2026-01-08T07:02:29","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2026\/01\/08\/2601-03533\/"},"modified":"2026-01-08T07:02:29","modified_gmt":"2026-01-08T07:02:29","slug":"2601-03533","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2026\/01\/08\/2601-03533\/","title":{"rendered":"Online Learning with Limited Information in the Sliding Window Model"},"content":{"rendered":"

Online Learning with Limited Information in the Sliding Window Model
\n \t

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

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

arXiv:2601.03533v1 Announce Type: new
\nAbstract: Motivated by recent work on the experts problem in the streaming model, we consider the experts problem in the sliding window model. The sliding window model is a well-studied model that captures applications such as traffic monitoring, epidemic tracking, and automated trading, where recent information is more valuable than older data. Formally, we have $n$ experts, $T$ days, the ability to query the predictions of $q$ experts on each day, a limited amount of memory, and should achieve the (near-)optimal regret $sqrt{nW}text{polylog}(nT)$ regret over any window of the last $W$ days. While it is impossible to achieve such regret with $1$ query, we show that with $2$ queries we can achieve such regret and with only $text{polylog}(nT)$ bits of memory. Not only are our algorithms optimal for sliding windows, but we also show for every interval $mathcal{I}$ of days that we achieve $sqrt{n|mathcal{I}|}text{polylog}(nT)$ regret with $2$ queries and only $text{polylog}(nT)$ bits of memory, providing an exponential improvement on the memory of previous interval regret algorithms. Building upon these techniques, we address the bandit problem in data streams, where $q=1$, achieving $n T^{2\/3}text{polylog}(T)$ regret with $text{polylog}(nT)$ memory, which is the first sublinear regret in the streaming model in the bandit setting with polylogarithmic memory; this can be further improved to the optimal $mathcal{O}(sqrt{nT})$ regret if the best expert’s losses are in a random order.<\/div>\n

\t

\n
<\/BR>
\n Vladimir Braverman, Sumegha Garg, Chen Wang, David P. Woodruff, Samson Zhou
\n \t

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

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

Online Learning with Limited Information in the Sliding Window Model arXiv:2601.03533v1 Announce Type: new Abstract: Motivated by recent work on the experts problem in the streaming model, we consider the experts problem in the sliding window model. The sliding window model is a well-studied model that captures applications such as traffic monitoring, epidemic tracking, and […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,413,113,112],"tags":[731,103,660],"class_list":["post-9581","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-ds","category-cs-lg","category-stat-ml","tag-memory","tag-model","tag-regret"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/9581"}],"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=9581"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/9581\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=9581"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=9581"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=9581"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}