Потоковые алгоритмы обучения с экспертами: детерминированные и робастные

В задаче онлайн-обучения с экспертами алгоритм должен делать предсказание исхода в каждый из T дней (или моментов времени), имея множество из n экспертов, которые делают предсказания в каждый день (или момент времени). Алгоритм получает обратную связь об исходах каждого дня, включая стоимость своего предсказания и стоимости предсказаний экспертов, а его цель — делать предсказания с минимальной стоимостью, в частности по сравнению с наилучшим экспертом в множестве. В недавней работе Srinivas, Woodruff, Xu и Zhou (STOC 2022) было положено начало изучению задачи онлайн-обучения с экспертами при ограничениях на память. Однако предсказания, сделанные экспертами или алгоритмами в некоторый момент времени, часто влияют на будущие исходы, поэтому входные данные выбираются адаптивно. Детерминированные алгоритмы устойчивы к адаптивным входным данным, тогда как существующие алгоритмы существенно используют рандомизацию для выборки небольшого числа экспертов. В этой статье мы исследуем детерминированные и робастные алгоритмы для задачи с экспертами. Сначала мы доказываем нижнюю оценку на объём памяти \(\widetilde{\Omega}\left(\frac{nM}{RT}\right)\) для любого детерминированного алгоритма, достигающего сожаления R, когда лучший эксперт допускает M ошибок. Наш результат показывает, что естественный детерминированный алгоритм, который перебирает группы экспертов до тех пор, пока каждый эксперт в группе не допустит ошибку, является оптимальным с точностью до полилогарифмических множителей. С другой стороны, мы предлагаем рандомизированный алгоритм, устойчивый к адаптивным входным данным, который использует \(\widetilde{O}\left(\frac{n}{R\sqrt{T}}\right)\) памяти при условии \(M=O\left(\frac{R^2 T}{\log^2 n}\right)\), тем самым демонстрируя плавный компромисс между объёмом памяти и сожалением.