Lazy OCO: Online Convex Optimization on a Switching Budget

Uri Sherman, Tomer Koren

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We study a variant of online convex optimization where the player is permitted to switch decisions at most S times in expectation throughout T rounds. Similar problems have been addressed in prior work for the discrete decision set setting, and more recently in the continuous setting but only with an adaptive adversary. In this work, we aim to fill the gap and present computationally efficient algorithms in the more prevalent oblivious setting, establishing a regret bound of O(T/S) for general convex losses and O˜(T/S2) for strongly convex losses. In addition, for stochastic i.i.d. losses, we present a simple algorithm that performs logT switches with only a multiplicative logT factor overhead in its regret in both the general and strongly convex settings. Finally, we complement our algorithms with lower bounds that match our upper bounds in some of the cases we consider.
اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفProceedings of Thirty Fourth Conference on Learning Theory
المحررونMikhail Belkin, Samory Kpotufe
الصفحات3972-3988
عدد الصفحات17
حالة النشرنُشِر - 2021

سلسلة المنشورات

الاسمProceedings of Machine Learning Research
ناشرPMLR
مستوى الصوت134

بصمة

أدرس بدقة موضوعات البحث “Lazy OCO: Online Convex Optimization on a Switching Budget'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا