Near-optimal algorithm with complexity separation for strongly convex-strongly concave composite saddle point problems

In this work, we revisit the saddle point problem minxmaxyp(x)+R(x,y)−q(y), where the function R(x,y) is LR-smooth, μx-strongly convex, and μy-strongly concave, and the functions p(x),q(y) are convex and Lp,Lq-smooth, respectively. We develop a new algorithm that achieves separation of complexities with respect to the computation of the gradients ∇R(x,y) and ∇p(x), ∇q(y). In particular, our algorithm requires O((LRμxμy+Lpμx+Lqμy4LRμx+LRμy+Lpμx+Lqμy)log⁡LRmin{μx,μy}log⁡1ε) computations of the gradient ∇R(x,y) and O((Lpμx+Lqμy)log⁡1ε) computations of the gradients ∇p(x), ∇q(y) to find an ϵ-accurate solution to the problem. Moreover, under the condition LR≥(μx+μy)μxμyμxLq+μyLp, the algorithm becomes optimal (up to logarithmic factors), i.e. it cannot be improved due to the existing lower complexity bounds. To the best of our knowledge, our algorithm is the first to achieve near-optimal complexity separation in the case when μx≠μy.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.