Adversarial Online Learning with Temporal Feedback Graphs

Khashayar Gatmiry, Jon Schneider
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4548-4572, 2024.

Abstract

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).

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-gatmiry24b, title = {Adversarial Online Learning with Temporal Feedback Graphs}, author = {Gatmiry, Khashayar and Schneider, Jon}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {4548--4572}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/gatmiry24b/gatmiry24b.pdf}, url = {https://proceedings.mlr.press/v247/gatmiry24b.html}, abstract = {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).} }
Endnote
%0 Conference Paper %T Adversarial Online Learning with Temporal Feedback Graphs %A Khashayar Gatmiry %A Jon Schneider %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-gatmiry24b %I PMLR %P 4548--4572 %U https://proceedings.mlr.press/v247/gatmiry24b.html %V 247 %X 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).
APA
Gatmiry, K. & Schneider, J.. (2024). Adversarial Online Learning with Temporal Feedback Graphs. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:4548-4572 Available from https://proceedings.mlr.press/v247/gatmiry24b.html.

Related Material