Рекуррентное агрегирование оценок методом зеркального спуска с усреднением

Рассматривается рекуррентный метод построения агрегированной оценки на конечном классе базовых решающих правил в задаче классификации. Оценка приближенно минимизирует выпуклый функционал риска при $\ell_1$-ограничении. Она задается стохастическим вариантом метода зеркального спуска, осуществляющего спуск градиентного типа в двойственном пространстве с дополнительным усреднением. Основной результат настоящей статьи – верхняя граница для средней точности предложенного алгоритма, имеющая порядок $C\sqrt{(\ln M)/t}$, с явным выражением малого постоянного множителя $C$, где $M$ – размерность задачи, $t$ – число наблюдений. Аналогичная граница получена и для более общей постановки, охватывающей, в частности, модель регрессии при квадратичных потерях.