2024-06-30-gatmiry24b.md

title	section	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
Adversarial Online Learning with Temporal Feedback Graphs	Original Papers	We study a variant of prediction with expert advice where the learner’s action at round $t$ is only allowed to depend on losses on a specific subset of the rounds (where the structure of which rounds’ losses are visible at time $t$ is provided by a directed “feedback graph” known to the learner). We present a novel learning algorithm for this setting based on a strategy of partitioning the losses across sub-cliques of this graph. We complement this with a lower bound that is tight in many practical settings, and which we conjecture to be within a constant factor of optimal. For the important class of transitive feedback graphs, we prove that this algorithm is efficiently implementable and obtains the optimal regret bound (up to a universal constant).	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	gatmiry24b	0	Adversarial Online Learning with Temporal Feedback Graphs	4548	4572	4548-4572	4548	false	Gatmiry, Khashayar and Schneider, Jon	given family Khashayar Gatmiry given family Jon Schneider	2024-06-30		Proceedings of Thirty Seventh Conference on Learning Theory	247	inproceedings	date-parts 2024 6 30	https://proceedings.mlr.press/v247/gatmiry24b/gatmiry24b.pdf