Penalized FTRL with Time-Varying Constraints

Conference paper (2023)

Authors

Douglas J. Leith Trinity College Dublin
G. Iosifidis Networked Systems - EEMCS
Research Group
Networked Systems (EEMCS) (TU Delft)
Copyright: © 2023 Douglas J. Leith, G. Iosifidis
DOI: https://doi.org/10.1007/978-3-031-26419-1_19
More Info
expand_more

Published Date

2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Software Technology

Research Group

Networked Systems

Abstract

In this paper we extend the classical Follow-The-Regularized-Leader (FTRL) algorithm to encompass time-varying constraints, through adaptive penalization. We establish sufficient conditions for the proposed Penalized FTRL algorithm to achieve O(t) regret and violation with respect to a strong benchmark X^tmax. Lacking prior knowledge of the constraints, this is probably the largest benchmark set that we can reasonably hope for. Our sufficient conditions are necessary in the sense that when they are violated there exist examples where O(t) regret and violation is not achieved. Compared to the best existing primal-dual algorithms, Penalized FTRL substantially extends the class of problems for which O(t) regret and violation performance is achievable.

Files

978_3_031_26419_1_19.pdf
(pdf | 0.507 Mb)
- Embargo expired in 17-09-2023