Corruption-Robust Lipschitz Contextual Search
This addresses robust online learning under adversarial corruptions for applications like pricing or recommendation systems, though it is incremental with new algorithmic techniques.
The paper tackles the problem of learning a Lipschitz function from corrupted binary signals, achieving regret bounds of L·O(C log T) for symmetric loss in 1D and L·O_d(C log T + T^{(d-1)/d}) for higher dimensions, and L·̃O(T^{d/(d+1)} + C·T^{1/(d+1)}) for pricing loss.
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 $x_t$ in the input space, and the learner makes a guess to the true function value $f(x_t)$ 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 \emph{unknown} to the learner. The learner's goal is to incur a small cumulative loss. This work introduces the new algorithmic technique \emph{agnostic checking} as well as new analysis techniques. I design algorithms which: for the symmetric loss, the learner achieves regret $L\cdot O(C\log T)$ with $d = 1$ and $L\cdot O_d(C\log T + T^{(d-1)/d})$ with $d > 1$; for the pricing loss, the learner achieves regret $L\cdot \widetilde{O} (T^{d/(d+1)} + C\cdot T^{1/(d+1)})$.