- Онлайн-обучение и решение бесконечных игр с ERM Oracle (arXiv)
Автор: Ангелос Ассос, Идан Аттиас, Ювал Даган, Константинос Даскалакис, Максвелл Фишелсон.
Аннотация: В то время как ERM достаточно для достижения почти оптимальной ошибки обобщения в условиях стохастического обучения, известно, что это не так в условиях онлайн-обучения, где алгоритмы для классов общих понятий полагаются на вычислительно неэффективные оракулы, такие как Стандартный оптимальный алгоритм ( СОА). В этой работе мы предлагаем алгоритм настройки двоичной классификации в режиме онлайн, который опирается исключительно на вызовы оракула ERM, и показываем, что он имеет конечное сожаление в реализуемых условиях и сублинейно растущее сожаление в агностических условиях. Мы связали сожаление с точки зрения Littlestone и пороговых измерений базового класса понятий. Мы получаем аналогичные результаты для непараметрических игр, где оракул ERM можно интерпретировать как оракул наилучшего ответа, находящий наилучший ответ игрока на заданную историю игры других игроков. В этом случае мы предоставляем алгоритмы обучения, которые полагаются только на оракулы наилучшего ответа и сходятся к приближенно-минимаксному равновесию в играх с нулевой суммой для двух игроков и к приближенному грубому коррелированному равновесию в многопользовательских играх с общей суммой, если игра имеет ограниченное жировое пороговое измерение. Наши алгоритмы применимы как к играм с двоичным значением, так и к играм с действительным значением, и их можно рассматривать как обоснование широкого использования алгоритмов двойного оракула и множественного оракула в практике решения больших игр.
2. Анализ методов нецелевой атаки и защиты от отравления для федеративного онлайн-обучения для ранжирования систем (arXiv)
Автор: Шуйи Ван, Гвидо Цуккон.
Абстрактный :
