Multi-point Feedback of Bandit Convex Optimization with Hard Constraints
This work addresses optimization under constraints with limited feedback, which is incremental as it builds on existing bandit convex optimization methods by introducing a new constraint metric and algorithm.
The paper tackles bandit convex optimization with hard constraints, where the learner aims to minimize cumulative loss and constraint violation under partial information, achieving sub-linear regret and constraint violation bounds of O(d^2T^{max{c,1-c}}) and O(d^2T^{1-c/2}) for convex loss functions, with further improvements for strongly convex functions.
This paper studies bandit convex optimization with constraints, where the learner aims to generate a sequence of decisions under partial information of loss functions such that the cumulative loss is reduced as well as the cumulative constraint violation is simultaneously reduced. We adopt the cumulative \textit{hard} constraint violation as the metric of constraint violation, which is defined by $\sum_{t=1}^{T} \max\{g_t(\boldsymbol{x}_t), 0\}$. Owing to the maximum operator, a strictly feasible solution cannot cancel out the effects of violated constraints compared to the conventional metric known as \textit{long-term} constraints violation. We present a penalty-based proximal gradient descent method that attains a sub-linear growth of both regret and cumulative hard constraint violation, in which the gradient is estimated with a two-point function evaluation. Precisely, our algorithm attains $O(d^2T^{\max\{c,1-c\}})$ regret bounds and $O(d^2T^{1-\frac{c}{2}})$ cumulative hard constraint violation bounds for convex loss functions and time-varying constraints, where $d$ is the dimensionality of the feasible region and $c\in[\frac{1}{2}, 1)$ is a user-determined parameter. We also extend the result for the case where the loss functions are strongly convex and show that both regret and constraint violation bounds can be further reduced.