1. Cautious regret minimization: Online optimization with long-term budget constraints
- Author
-
Liakopoulos, Nikolaos, Destounis, Apostolos, Paschos, Georgios, Spyropoulos, Thrasyvoulos, Mertikopoulos, Panayotis, Huawei Technologies France, Huawei Technologies France [Boulogne-Billancourt], Informatics & Telematics Institute (ITI), CERTH, Eurecom [Sophia Antipolis], Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), ANR-16-CE33-0004,ORACLESS,Stratégies adaptatives d'allocation des ressources dans les réseaux sans fil dynamiques(2016), HUAWEI Technologies France (HUAWEI), Alcatel Lucent Bell Labs, ALCATEL, and Huawei Technologies France [Boulogne-Billancour]
- Subjects
[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] - Abstract
International audience; 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.
- Published
- 2019