Graduate School and Research Center in Digital Sciences

Cautious regret minimization: Online optimization with long-term budget constraints

Liakopoulos, Nikolaos; Destounis, Apostolos; Paschos, Georgios; Spyropoulos, Thrasyvoulos; Mertikopoulos, Panayotis

ICML 2019, 36th International Conference on Machine Learning, 9-15 June 2019, Long Beach, California, USA

We study a class of online convex optimization problems with long-term budget constraints that arise naturally as reliability guarantees or total consumption constraints. In this general setting, prior work by Mannor et al. (2009) has shown that achieving no regret is impossible if the functions defining the agent's budget are chosen by an adversary. To overcome this obstacle, we refine the agent's regret metric by introducing the notion of a "K-benchmark", i.e., a comparator which meets the problem's allotted budget over any window of length K. The impossibility analysis of Mannor et al. (2009) is recovered when K = T; however, for K = o(T), we show that it is possible to minimize regret while still meeting the problem's long-term budget constraints. We achieve this via an online learning algorithm based on cautious online Lagrangian descent (COLD) for which we derive explicit bounds, in terms of both the incurred regret and the residual budget violations.

Document Hal Bibtex

Title:Cautious regret minimization: Online optimization with long-term budget constraints
Type:Conference
Language:English
City:Long Beach
Country:UNITED STATES
Date:
Department:Communication systems
Eurecom ref:5929
Copyright: © 2019 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @inproceedings{EURECOM+5929, year = {2019}, title = {{C}autious regret minimization: {O}nline optimization with long-term budget constraints}, author = {{L}iakopoulos, {N}ikolaos and {D}estounis, {A}postolos and {P}aschos, {G}eorgios and {S}pyropoulos, {T}hrasyvoulos and {M}ertikopoulos, {P}anayotis}, booktitle = {{ICML} 2019, 36th {I}nternational {C}onference on {M}achine {L}earning, 9-15 {J}une 2019, {L}ong {B}each, {C}alifornia, {USA}}, address = {{L}ong {B}each, {UNITED} {STATES}}, month = {06}, url = {http://www.eurecom.fr/publication/5929} }
See also: