Corruption-Robust Lipschitz Contextual Search

I study the problem of learning a Lipschitz function with corrupted binary signals. The learner tries to learn a L-Lipschitz function f: [0,1]d rightarrow [0, L] that the adversary chooses. There is a total of T rounds. In each round t, the adversary selects a context vector xt in the input space, and the learner makes a guess to the true function value f(xt) and receives a binary signal indicating whether the guess is high or low. In a total of C rounds, the signal may be corrupted, though the value of C is unknown to the learner. The learner's goal is to incur a small cumulative loss. This work introduces the new algorithmic technique agnostic checking as well as new analysis techniques. I design algorithms which: for the symmetric loss, the learner achieves regret L· O(Clog T) with d = 1 and L· Od(Clog T + T(d-1)/d) with d > 1; for the pricing loss, the learner achieves regret L· widetildeO (Td/(d+1) + C· T1/(d+1)).