Обзор современных рандомизированных безградиентных алгоритмов для задач выпуклой оптимизации

Для решения задач, когда процесс вычисления градиента функции является слишком дорогим или вовсе, по каким-либо причинам, недоступным, на помощь приходят техники создания безградиентных алгоритмов (где "безградиентный" оракул возвращает только значение целевой функции в запрошенной точке с, возможно, ограниченным шумом). В зависимости от задачи, в частности, от информации о целевой функции, создается безградиентный алгоритм, основанный на вычислении аппроксимации градиента функции вместо истинного градиента. В качестве критерия оптимальности безградиентного алгоритма выделяют следующее: общее число итераций для достижения желаемой точности, оракульная сложность и максимально допустимый уровень "враждебного" шума, при котором ещё можно достичь желаемой точности. В этом докладе будут представлены безградиентные алгоритмы для следующих настроек задачи: негладкая задача оптимизации в архитектуре федеративного обучения, негладкая задача оптимизации с ограничениями, гладкая задача оптимизации с условием перепараметризации, а также задача оптимизации с условием Поляка-Лоясиевича.