Corruption-Robust Contextual Search through Density Updates

Renato Paes Leme, Chara Podimata, Jon Schneider
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:3504-3505, 2022.

Abstract

We study the problem of contextual search 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 noise in the system. For the $\epsilon$-ball loss, we give a tight regret bound of $O(C + d \log(1/\epsilon))$ improving over the $O(d^3 \log(1/\epsilon)) \log^2(T) + C \log(T) \log(1/\epsilon))$ bound of Krishnamurthy et al (STOC’21). For the symmetric loss, we give an efficient algorithm with regret $O(C+d \log T)$. In terms of techniques, our algorithms are a departure from previous contextual search models in the sense that they keep track of density functions over the candidate vectors instead of a knowledge set consisting of the candidate vectors consistent with the feedback obtained.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-leme22a, title = {Corruption-Robust Contextual Search through Density Updates}, author = {Leme, Renato Paes and Podimata, Chara and Schneider, Jon}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {3504--3505}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/leme22a/leme22a.pdf}, url = {https://proceedings.mlr.press/v178/leme22a.html}, abstract = {We study the problem of contextual search 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 noise in the system. For the $\epsilon$-ball loss, we give a tight regret bound of $O(C + d \log(1/\epsilon))$ improving over the $O(d^3 \log(1/\epsilon)) \log^2(T) + C \log(T) \log(1/\epsilon))$ bound of Krishnamurthy et al (STOC’21). For the symmetric loss, we give an efficient algorithm with regret $O(C+d \log T)$. In terms of techniques, our algorithms are a departure from previous contextual search models in the sense that they keep track of density functions over the candidate vectors instead of a knowledge set consisting of the candidate vectors consistent with the feedback obtained.} }
Endnote
%0 Conference Paper %T Corruption-Robust Contextual Search through Density Updates %A Renato Paes Leme %A Chara Podimata %A Jon Schneider %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-leme22a %I PMLR %P 3504--3505 %U https://proceedings.mlr.press/v178/leme22a.html %V 178 %X We study the problem of contextual search 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 noise in the system. For the $\epsilon$-ball loss, we give a tight regret bound of $O(C + d \log(1/\epsilon))$ improving over the $O(d^3 \log(1/\epsilon)) \log^2(T) + C \log(T) \log(1/\epsilon))$ bound of Krishnamurthy et al (STOC’21). For the symmetric loss, we give an efficient algorithm with regret $O(C+d \log T)$. In terms of techniques, our algorithms are a departure from previous contextual search models in the sense that they keep track of density functions over the candidate vectors instead of a knowledge set consisting of the candidate vectors consistent with the feedback obtained.
APA
Leme, R.P., Podimata, C. & Schneider, J.. (2022). Corruption-Robust Contextual Search through Density Updates. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:3504-3505 Available from https://proceedings.mlr.press/v178/leme22a.html.

Related Material