Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback

Shanqi Liu, Xin Liu 1 · 2024

Read Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback by Shanqi Liu, Xin Liu 1 (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03983.txt.

Introduction

Shanqi Liu and Xin Liu study safe online choices under a tight budget in a 2024 paper. The setting is a stream of choices where each pick earns a gain but spends from a budget that is not known in full ahead of time. Only past spend reports come back, so the learner must feel its way without ever busting the cap.

Their method leans on a Lyapunov style guide that keeps a virtual queue in check. It pairs a clean inner solve with a plain dual update, so each step stays cheap to run. They prove the loss against the best fixed plan grows only with the square root of time, while total cap breaks stay at zero. A data center energy task test backs the math.

Catalog record

CREATORShanqi Liu, Xin Liu 1
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-03983

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback Thanks: 1 Corresponding Author. Shanqi Liu, Xin Liu 1 Abstract 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 ) O(\sqrt{T}) regret and zero cumulative constraint violation. The result also implies SELO achieves O ⁡ ( T ) 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. I Introduction Online Convex Optimization (OCO) provides a versatile framework for studying online control and decision-making in dynamic and uncertain environments [ 1 , 2 , 3 ] . Within this framework, a learner/controller continuously adapts its decisions to minimize a loss function or maximize a utility function while interacting with the environment in real-time. OCO has wide-ranging applications, including robotics control [ 4 , 5 , 6 ] , resource allocation in network systems [ 7 , 8 , 9 , 10 , 11 , 12 ] , load balancing in server systems [ 13 , 14 , 15 ] , online advertising [ 16 , 17 ] , and personalized healthcare [ 18 , 19 ] . In OCO framework, the learner/controller chooses a decision x_{t} in each round without prior knowledge of the convex loss function f_{t}(\cdot) . The objective is to minimize the total loss over T rounds, given by \min_{x\in\mathcal{X}}\sum_{t=1}^{T}f_{t}(x_{t}), where the loss incurred by each decision x_{t} is observed only after the decision has been executed. In real-world scenarios, these interactions are usually constrained by operational budgets. For instance, in a cloud computing system, the data center optimizes the throughput or delay performance within an energy budget; in online advertising, advertisers submit bids to maximize the click-through rates within a weekly or monthly budget. Similarly, inpatient onboarding, hospitals optimize patients’ treatment by assigning them to proper medical units under medical resources constraints. In these applications, the operational constraints usually have a linear form, and the consumption matrix ( A_{t} ) is unknown, where only the partial feedback can be observed in practice (i.e., the gradient/values of loss functions \nabla f(x_{t})/f(x_{t}) and the values of resource consumption A_{t}x_{t} of the decision point x_{t} ). To model these applications, we study online convex optimization with linear budget constraints (OCOwLB) with partial feedback \displaystyle\min_{x_{t}\in\mathcal{X}} \displaystyle~\sum_{t=1}^{T}f_{t}(x_{t}) s.t. \displaystyle~\sum_{t=1}^{T}A_{t}x_{t}\leq B where \nabla f(x_{t})/f(x_{t}) and A_{t}x_{t} are revealed to the learner after the decision x_{t} is taken. In OCOwLB, the learner aims to minimize the total loss with only partial feedback while satisfying the budget constraints or keeping the constraint violation minimal. One possible method to satisfy the budget constraints is to identify the underlying (expected) static constraints and project the decision x_{t} into a safe (strictly feasible) set at each round [ 20 , 21 , 22 , 23 , 24 , 25 , 26 ] . However, such “anytime safe projection” methods may encounter three potential challenges when dealing with budget constraints: 1) they often require a substantial initial period to explore and learn the consumption matrix; 2) determining the “correct” safe constraint set based on an estimated consumption matrix is difficult and they are very likely to be overly conservative ensures safety but degrades performance; 3) the projection-based methods (e.g., projected online gradient descent) may require heavy computation because it is equivalent to solving a constrained quadratic optimization problem or could be almost extremely challenging (if not unsolvable) due to the non-convexity of the constraint set. In this paper, we propose a safe and efficient Lyapunov-optimization (SELO) algorithm for OCOwLB with partial feedback that achieves strong theoretical results. Next, we summarize our main contributions. Main Contribution: SELO is motivated by the primal-dual design and Lyapunov optimization framework. The primal decision modular incorporates the estimated loss function and the virtual queues that capture the over-used resource to balance the loss minimization and resource consumption. It is computationally efficient because the primal problem is (almost) unconstrained, strongly convex, and smooth. The virtual queues \{Q_{t}\} are designed to capture the cumulative overused budgets. In particular, we impose a “pessimistic” bonus term and “pessimistic” penalty term to guarantee the “safety” due to the initial exploration phase. SELO achieves O(\sqrt{T}) regret and zero constraint violation. We apply SELO to low-delay task processing in distributed data centers with energy budget constraints. Our experimental results demonstrate that SELO outperforms baseline algorithms and performs similarly against the optimal offline policy. II Related work Safe online learning with partial/bandit feedback has been studied in the literature mainly from the perspective of constrained online convex optimization (COCO) [ 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 37 , 38 ] and constrained bandit optimization (CBO) [ 39 , 40 , 41 , 42 , 43 , 44 , 45 , 46 , 47 , 48 , 49 , 50 , 51 , 52 , 53 , 54 , 55 ] . COCO : The work [ 27 ] initialized the studies of COCO and proposed an algorithm that achieves O(\sqrt{T}) regret and O(T^{3/4}) violation for static constraints and it is further extended to the setting where the constraints could be stochastic, time-varying or adversarial [ 28 , 29 , 30 , 31 , 32 , 33 ] , where the representative work [ 30 ] established O(\sqrt{T}) regret and O(\sqrt{T}) constraint violation for stochastic and adversarial constraints when the Slater’s condition holds. The work [ 34 ] studied COCO under the strict metric of hard constraint violation where the violation cannot compensate and established O(\sqrt{T}) regret and O(T^{3/4}) hard violation for static constraints. The results is further improved to O(\sqrt{T}) regret and O(T^{1/4}) violation in [ 35 ] and O(\sqrt{T}) regret and O(1) violation in [ 36 ] . When the constraint is adversarial, the work [ 36 ] also proved O(\sqrt{T}) regret and O(T^{3/4}) hard violation and a recent remarkable work [ 38 ] established O(\sqrt{T}) regret and O(\sqrt{T}\log T) by designing a clever Lyapunov function integrated into adaptive online gradient descent. Unlike COCO with full information feedback, we only have partial feedback on the constraints. CBO : The work [ 39 , 40 ] initialized the studies of CBO by introducing the problem of Bandit with Knapsack and proposed the algorithms (e.g., PrimalDualBwK) that achieve effective regret performance. BwK is further extended to various settings, including context (linear) bandit [ 41 , 42 ] , adversarial setting [ 43 , 44 , 45 ] , fairness constraints [ 46 , 47 ] , general constraints [ 48 , 50 ] , and small budget setting [ 51 ] . These algorithms carefully balance the reward acquisition and resource consumption by using the idea of primal-dual optimization more or less. Note another

Read the complete text