# Multi-point Feedback of Bandit Convex Optimization with Hard Constraints

arXiv: https://arxiv.org/abs/2310.10946 · HTML: https://mlsanity.com/paper/2310.10946/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 24 references that are in the map.
- First posted on arXiv 17 Oct 2023.

## Builds on (most cited first, 10 of 10)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [Projection-Free Bandit Convex Optimization](https://mlsanity.com/paper/1805.07474/) (2018)
- [Improved Regret Bounds for Projection-free Bandit Convex Optimization](https://mlsanity.com/paper/1910.03374/) (2019)
- [Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraints](https://mlsanity.com/paper/2211.14720/) (2022)

## Abstract (arXiv)

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 textithard constraint violation as the metric of constraint violation, which is defined by sumt=1T maxgt(boldsymbolxt), 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 textitlong-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(d2T^maxc,1-c) regret bounds and O(d2T^1-fracc2) cumulative hard constraint violation bounds for convex loss functions and time-varying constraints, where d is the dimensionality of the feasible region and c∈[frac12, 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.