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
Beyond Separability: Analyzing the Linear Transferability of Contrastive Representations to Related Subpopulations
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Communication Efficient Distributed Learning for Kernelized Contextual Bandits
Watch later
Chuanhao Li, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Generalised Implicit Neural Representations
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Revisiting Injective Attacks on Recommender Systems
Watch later
Haoyang Li, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
BinauralGrad: A Two-Stage Conditional Diffusion Probabilistic Model for Binaural Audio Synthesis
Watch later
Yichong Leng, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Byzantine-Tolerant Federated Gaussian Process Regression for Streaming Data
Watch later
Xu Zhang, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%