2022-06-28-leme22a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Corruption-Robust Contextual Search through Density Updates	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.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	leme22a	0	Corruption-Robust Contextual Search through Density Updates	3504	3505	3504-3505	3504	false	Leme, Renato Paes and Podimata, Chara and Schneider, Jon	given family Renato Paes Leme given family Chara Podimata given family Jon Schneider	2022-06-28		Proceedings of Thirty Fifth Conference on Learning Theory	178	inproceedings	date-parts 2022 6 28	https://proceedings.mlr.press/v178/leme22a/leme22a.pdf