Ускорение сведением к седловым задачам с приложением к поиску барицентров Вассерштейна

Популярность седловых задач в последнее время обусловлена различными практическими задачами, в том числе, обучением моделей GAN. В общем случае, такие задачи можно считать более сложным классом, чем обычные задачи выпуклой минимизации, но при этом в некоторых случаях сведение задачи к седловой может дать, например, алгоритм, сравнимый с наилучшими, но численно более стабильный ([1] и [2]), а как максимум – улучшение асимптотики. Ярким примером последнего является недавняя работа [2], где, используя более общее семество регуляризаторов для седловых задач, называемых area-convex регуляризаторами, получилась лучшая известная асимптотика для задачи поиска барицентров Вассерштейна, которая, скорее всего, является неулучшаемой.
Доклад основан на следующих работах:
[1] Stochastic Saddle-Point Optimization for Wasserstein Barycenters (Daniil Tiapkin, Alexander Gasnikov, Pavel Dvurechensky) [2] Improved Complexity Bounds in Wasserstein Barycenter Problem (Darina Dvinskikh, Daniil Tiapkin)