Non-euclidean proximal methods for convex-concave saddle-point problems

被引：0
作者：
Cohen E. [1 ]
Sabach S. [2 ]
Teboulle M. [1 ]
机构：
[1] School of Mathematical Sciences, Tel-Aviv University, Ramat-Aviv
[2] Faculty of Industrial Engineering, Technion, Haifa
来源：
Journal of Applied and Numerical Optimization | 2021年 / 3卷 / 01期
基金：
以色列科学基金会;
关键词：
Bregman and ϕ-divergences; Convergence rate; Iteration complexity; Non-Euclidean proximal distances and algorithms; Nonsmooth convex minimization; Saddle-point problems;
D O I：
10.23952/jano.3.2021.1.04
中图分类号：
学科分类号：
摘要：
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. © 2021 Journal of Applied and Numerical Optimization.
引用
收藏
页码：43 / 60
页数：17
相关论文
共 29 条
  • [1] Korpelevic G. M., An extragradient method for finding saddle-points and for other problems, Èkonom. i Mat. Metody, 12, pp. 747-756, (1976)
  • [2] Nemirovski A., Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle-point problems, SIAM J. Optim, 15, pp. 229-251, (2004)
  • [3] Auslender A., Teboulle M., Interior projection-like methods for monotone variational inequalities, Math. Program. Ser. A, 104, pp. 39-68, (2005)
  • [4] Lions P. L., Mercier B., Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal, 16, pp. 964-979, (1979)
  • [5] Passty G. B., Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. Math. Anal. Appl, 72, pp. 383-390, (1979)
  • [6] Gabay D., Applications of the Method of Multipliers to Variational Inequalities, Studies in Mathematics and Its Applications, 15, pp. 299-331, (1983)
  • [7] Glowinski R., Le Tallec P., Augmented Lagrangian and operator splitting methods in nonlinear mechanics, (1989)
  • [8] Sabach S., Teboulle M., Lagrangian methods for composite optimization, Handbook of Numerical Analysis, 20, pp. 401-436, (2019)
  • [9] Nesterov Y., Smooth minimization of non-smooth functions, Math. Program. Ser. A, 103, pp. 127-152, (2005)
  • [10] Beck A., Teboulle M., Smoothing and first order methods: a unified framework, SIAM J. Optim, 22, pp. 557-580, (2012)
123