Timezone: »

Poster
Online Forecasting of Total-Variation-bounded Sequences
Dheeraj Baby · Yu-Xiang Wang

Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #22
We consider the problem of online forecasting of sequences of length $n$ with total-variation at most $C_n$ using observations contaminated by independent $\sigma$-subgaussian noise. We design an $O(n\log n)$-time algorithm that achieves a cumulative square error of $\tilde{O}(n^{1/3}C_n^{2/3}\sigma^{4/3} + C_n^2)$ with high probability. We also prove a lower bound that matches the upper bound in all parameters (up to a $\log(n)$ factor). To the best of our knowledge, this is the first **polynomial-time** algorithm that achieves the optimal $O(n^{1/3})$ rate in forecasting total variation bounded sequences and the first algorithm that **adapts to unknown** $C_n$.Our proof techniques leverage the special localized structure of Haar wavelet basis and the adaptivity to unknown smoothness parameters in the classical wavelet smoothing [Donoho et al., 1998]. We also compare our model to the rich literature of dynamic regret minimization and nonstationary stochastic optimization, where our problem can be treated as a special case. We show that the workhorse in those settings --- online gradient descent and its variants with a fixed restarting schedule --- are instances of a class of **linear forecasters** that require a suboptimal regret of $\tilde{\Omega}(\sqrt{n})$. This implies that the use of more adaptive algorithms is necessary to obtain the optimal rate.
{"ft_lang_label":"__label__en","ft_lang_prob":0.5317433,"math_prob":0.99243087,"size":6930,"snap":"2023-14-2023-23","text_gpt3_token_len":1829,"char_repetition_ratio":0.17874674,"word_repetition_ratio":0.14494075,"special_character_ratio":0.24473305,"punctuation_ratio":0.063969895,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9954823,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-06-10T07:37:35Z\",\"WARC-Record-ID\":\"<urn:uuid:2cf2fdb6-aa85-4771-94c8-897f344d4f96>\",\"Content-Length\":\"56302\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:c990c078-d0cc-4e94-a7ee-e1db28aff1ae>\",\"WARC-Concurrent-To\":\"<urn:uuid:447892af-3a69-4e4c-83ea-b52ddcc05c8e>\",\"WARC-IP-Address\":\"198.202.70.65\",\"WARC-Target-URI\":\"https://neurips.cc/Conferences/2019/ScheduleMultitrack?event=14103\",\"WARC-Payload-Digest\":\"sha1:67XS3YED7N2BWKJMXPIH3ELYR5ZVSH67\",\"WARC-Block-Digest\":\"sha1:GEHHK5IWANUOLKICMCM7K4VKKQAANAYH\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224657144.94_warc_CC-MAIN-20230610062920-20230610092920-00352.warc.gz\"}"}