This work studies Lipschitz contextual search with adversarial corruptions. Contextual search is a generalization of the classic binary search to higher dimensions, with applications in dynamic pricing and personalized medicine. We study contextual search in a non-parametric setting, where a learner tries to learn a L-Lipschitz function f:[0,1]^d→[0,L] that the adversary chooses. There is a total of T rounds, in each round the adversary presents the learner with context x, and the learner makes a guess to f(x) and can observe whether his guess is low or high. We further allow some signals to be corrupted. In at most C rounds the signal may be flipped, though the value of C is unknown to the learner. The learner's goal is to incur a small cumulative loss that degrade gracefully as C increases.
>>
>> This work introduces a new algorithmic technique “agnostic corruption checks” as well as new analysis techniques. We design algorithms which: for the absolute loss, the learner achieves regret L⋅O(ClogT) when d=1 and L⋅O_d(ClogT+T^(d−1)/d) when d>1; for the pricing loss, the learner achieves regret L⋅Õ(T^d/(d+1)+C⋅T^1/(d+1)).
