Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback
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(\sqrt{T})$ regret and zero cumulative constraint violation. The result also implies SELO achieves $O(\sqrt{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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Safe Online Convex Optimization with Unknown Linear Safety Constraints
We study the problem of safe online convex optimization, where the action at each time step must satisfy a set of linear safety constraints. The goal is to select a sequence of actions to minimize the regret without viol…
Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty
In online marketing, the advertisers' goal is usually a tradeoff between achieving high volumes and high profitability. The companies' business units customarily address this tradeoff by maximizing the volumes while guar…
MarketingDynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems
This paper addresses safe distributed online optimization over an unknown set of linear safety constraints. A network of agents aims at jointly minimizing a global, time-varying function, which is only partially observab…
Safety Filter Design for Neural Network Systems via Convex Optimization
With the increase in data availability, it has been widely demonstrated that neural networks (NN) can capture complex system dynamics precisely in a data-driven manner. However, the architectural complexity and nonlinear…
Bi-Level Online Provisioning and Scheduling with Switching Costs and Cross-Level Constraints
We study a bi-level online provisioning and scheduling problem motivated by network resource allocation, where provisioning decisions are made at a slow time scale while queue-/state-dependent scheduling is performed at …