Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization
This work addresses corruption-robust optimization in machine learning, offering incremental improvements in regret bounds for contextual search and convex optimization problems.
The paper tackles the problem of contextual search with adversarial noise, providing improved regret bounds: for the ε-ball loss, they achieve O(C + d log(1/ε)), and for the symmetric loss, they develop an efficient algorithm with O(C + d log T) regret.
We study the problem of contextual search, a generalization of binary search in higher dimensions, in the adversarial noise model. Let $d$ be the dimension of the problem, $T$ be the time horizon and $C$ be the total amount of adversarial noise in the system. We focus on the $ε$-ball and the symmetric loss. For the $ε$-ball loss, we give a tight regret bound of $O(C + d \log(1/ε))$ improving over the $O(d^3 \log(1/ε) \log^2(T) + C \log(T) \log(1/ε))$ bound of Krishnamurthy et al (Operations Research '23). For the symmetric loss, we give an efficient algorithm with regret $O(C+d \log T)$. To tackle the symmetric loss case, we study the more general setting of Corruption-Robust Convex Optimization with Subgradient feedback, which is of independent interest. Our techniques are a significant departure from prior approaches. Specifically, we keep track of density functions over the candidate target vectors instead of a knowledge set consisting of the candidate target vectors consistent with the feedback obtained.