A Unifying Framework for Online Optimization with Long-Term Constraints
Nov 28, 2022
Speakers
Matteo Castiglioni
Speaker · 0 followers
Andrea Celli
Speaker · 0 followers
Alberto Marchesi
Speaker · 1 follower
Giulia Romano
Speaker · 0 followers
Nicola Gatti
Speaker · 0 followers
About
We study online learning problems in which a decision maker has to take a sequence of decisions subject to m long-term constraints. The goal of the decision maker is to maximize their total reward, while at the same time achieving small cumulative constraints violations across the T rounds. We present the first best-of-both-world type algorithm for this general class of problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown stochastic model, and in the case in which they are selected at each round by an adversary. Our algorithm is the first to provide guarantees in the adversarial setting with respect to the optimal fixed strategy that satisfies the long-term constraints. In particular, it guarantees a ρ/(1+ρ) fraction of the optimal utility and sublinear regret, where ρ is a feasibility parameter related to the existence of strictly feasible solutions. Our framework employs traditional regret minimizers as black-box components. Therefore, by instantiating it with an appropriate choice of regret minimizers it can handle both the full-feedback as well as the bandit-feedback setting. Moreover, it allows the decision maker to seamlessly handle scenarios with non-convex reward and constraints. We show how our framework may be applied in the context of budget-management mechanisms for repeated auctions in order to guarantee long-term constraints which are not packing (e.g., ROI constraints).We study online learning problems in which a decision maker has to take a sequence of decisions subject to m long-term constraints. The goal of the decision maker is to maximize their total reward, while at the same time achieving small cumulative constraints violations across the T rounds. We present the first best-of-both-world type algorithm for this general class of problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown stoc…
Organizer
NeurIPS 2022
Account · 952 followers
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Accelerated Algorithms for Monotone Inclusion and Constrained Nonconvex-Nonconcave Min-Max Optimization
Watch later
Yang Cai, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Variational Model Perturbation for Source-Free Domain Adaptation
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Inception Transformer
Watch later
Chenyang Si, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
HAPI: A Large-scale Longitudinal Dataset of Commercial ML API Predictions
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Differentially Private Model Compression
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Rotation-Equivariant Conditional Spherical Neural Fields for Learning a Natural Illumination Prior
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%