Skip to content

Eyal Cohen, Shoham Sabach, Marc Teboulle, Non-Euclidean proximal methods for convex-concave saddle-point problems

Full Text: PDF
DOI: 10.23952/jano.3.2021.1.04
Volume 3, Issue 1, 30 April 2021, PagesĀ 43-60

 

Abstract. Motivated by the flexibility of the Proximal Alternating Predictor Corrector (PAPC) algorithm which can tackle a broad class of structured constrained convex optimization problems via their convex-concave saddle-point reformulation, in this paper, we extend the scope of the PAPC algorithm to include non-Euclidean proximal steps. This allows for adapting to the geometry of the problem at hand to produce simpler computational steps. We prove a sublinear convergence rate of the produced ergodic sequence, and under additional natural assumptions on the non-Euclidean distances, we also prove that the algorithm globally converges to a saddle-point. We demonstrate the performance and simplicity of the proposed algorithm through its application to the multinomial logistic regression problem.

 

How to Cite this Article:
Eyal Cohen, Shoham Sabach, Marc Teboulle, Non-Euclidean proximal methods for convex-concave saddle-point problems, J. Appl. Numer. Optim. 3 (2021), 43-60.