Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback
Not on the map. Why?
Abstract (arXiv)
This paper studies online convex optimization with unknown linear budget constraints, where only the gradient information of the objective and the bandit feedback of constraint functions are observed. We propose a safe and efficient Lyapunov-optimization algorithm (SELO) that can achieve an O(√T) regret and zero cumulative constraint violation. The result also implies SELO achieves O(√T) regret when the budget is hard and not allowed to be violated. The proposed algorithm is computationally efficient as it resembles a primal-dual algorithm where the primal problem is an unconstrained, strongly convex and smooth problem, and the dual problem has a simple gradient-type update. The algorithm and theory are further justified in a simulated application of energy-efficient task processing in distributed data centers.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 34 of its 65 references that are in the map. First posted on arXiv 5 Dec 2024.
Builds on
34 of 65 references.
References · 34
- 2021Convex optimizationcited by 2,515
- 2019Introduction to Online Convex Optimizationcited by 803
- 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
- 2022On the Convergence Rates of Policy Gradient Methodscited by 119
- 2017Online Convex Optimization with Stochastic Constraintscited by 95
- 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
- 2015Linear Contextual Bandits with Knapsackscited by 82
- 2020Stochastic Bandits with Linear Constraintscited by 68
- 2017Online Convex Optimization with Time-Varying Constraintscited by 56
- 2020Dual Mirror Descent for Online Allocation Problemscited by 52
- 2018Online convex optimization for cumulative constraintscited by 47
- 2014Resourceful Contextual Banditscited by 45
22 more
- 2017An Online Convex Optimization Approach to Dynamic Network Resource Allocationcited by 42
- 2019Fair Contextual Multi-Armed Bandits: Theory and Experimentscited by 42
- 2021Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraintscited by 39
- 2019Safe Linear Thompson Sampling with Side Informationcited by 37
- 2023Optimal Algorithms for Online Convex Optimization with Adversarial Constraintscited by 34
- 2019An Online Learning Approach to Model Predictive Controlcited by 30
- 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
- 2021An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraintscited by 29
- 2016Matching while Learningcited by 19
- 2022Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Riskcited by 15
- 2022Safe Linear Bandits over Unknown Polytopescited by 14
- 2021Safe Online Convex Optimization with Unknown Linear Safety Constraintscited by 13
- 2022Learning to Optimize in Model Predictive Controlcited by 11
- 2021Dual Online Stein Variational Inference for Control and Dynamicscited by 10
- 2023BanditQ: Fair Bandits with Guaranteed Rewardscited by 6
- 2023Bandits with Replenishable Knapsacks: the Best of both Worldscited by 6
- 2018Learning Aided Optimization for Energy Harvesting Devices with Outdated State Informationcited by 5
- 2023Online Nonstochastic Control with Adversarial and Static Constraintscited by 5
- 2023Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problemscited by 4
- 2016Stochastic Averaging for Constrained Optimization with Application to Online Resource Allocationcited by 3
- 2024Testing the Feasibility of Linear Programs with Bandit Feedbackcited by 3
- 2024Optimistic Safety for Online Convex Optimization with Unknown Linear Constraintscited by 1
Built on by
Not cited yet.