Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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 type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-02405753
Contributor : Panayotis Mertikopoulos <>
Submitted on : Wednesday, December 11, 2019 - 7:03:21 PM
Last modification on : Tuesday, May 11, 2021 - 11:37:50 AM
Long-term archiving on: : Thursday, March 12, 2020 - 11:09:38 PM

File

BudgetRegret-ICML.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02405753, version 1

Citation

Nikolaos Liakopoulos, Apostolos Destounis, Georgios Paschos, Thrasyvoulos Spyropoulos, Panayotis Mertikopoulos. Cautious regret minimization: Online optimization with long-term budget constraints. ICML 2019 - 36th International Conference on Machine Learning, Jun 2019, Long Beach, United States. pp.1-9. ⟨hal-02405753⟩

Share

Metrics

Record views

88

Files downloads

361