Corruption-Robust Lipschitz Contextual Search

Shiliang Zuo
Proceedings of The 35th International Conference on Algorithmic Learning Theory, PMLR 237:1234-1254, 2024.

Abstract

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→[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 absolute loss, the learner achieves regret L⋅O(ClogT) when d=1 and L⋅Od(ClogT+T(d−1)/d) when d>1; for the pricing loss, the learner achieves regret L⋅˜O(Td/(d+1)+C⋅T1/(d+1)).

Cite this Paper

BibTeX
@InProceedings{pmlr-v237-zuo24a, title = {Corruption-Robust Lipschitz Contextual Search}, author = {Zuo, Shiliang}, booktitle = {Proceedings of The 35th International Conference on Algorithmic Learning Theory}, pages = {1234--1254}, year = {2024}, editor = {Vernade, Claire and Hsu, Daniel}, volume = {237}, series = {Proceedings of Machine Learning Research}, month = {25--28 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v237/zuo24a/zuo24a.pdf}, url = {https://proceedings.mlr.press/v237/zuo24a.html}, abstract = {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 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 absolute loss, the learner achieves regret $L\cdot O(C\log T)$ when $d = 1$ and $L\cdot O_d(C\log T + T^{(d-1)/d})$ when $d > 1$; for the pricing loss, the learner achieves regret $L\cdot \widetilde{O} (T^{d/(d+1)} + C\cdot T^{1/(d+1)})$. } }
Endnote
%0 Conference Paper %T Corruption-Robust Lipschitz Contextual Search %A Shiliang Zuo %B Proceedings of The 35th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Claire Vernade %E Daniel Hsu %F pmlr-v237-zuo24a %I PMLR %P 1234--1254 %U https://proceedings.mlr.press/v237/zuo24a.html %V 237 %X 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 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 absolute loss, the learner achieves regret $L\cdot O(C\log T)$ when $d = 1$ and $L\cdot O_d(C\log T + T^{(d-1)/d})$ when $d > 1$; for the pricing loss, the learner achieves regret $L\cdot \widetilde{O} (T^{d/(d+1)} + C\cdot T^{1/(d+1)})$.
APA
Zuo, S.. (2024). Corruption-Robust Lipschitz Contextual Search. Proceedings of The 35th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 237:1234-1254 Available from https://proceedings.mlr.press/v237/zuo24a.html.

Related Material