Accelerated variance-reduced methods for saddle-point problems

Ekaterina Borodich; Vladislav Tominin; Yaroslav Tominin; Dmitry Kovalev; Alexander Gasnikov; Pavel Dvurechensky

doi:10.1016/j.ejco.2022.100048

Accelerated variance-reduced methods for saddle-point problems

Ekaterina Borodich, Vladislav Tominin, Yaroslav Tominin, Dmitry Kovalev, Alexander Gasnikov, Pavel Dvurechensky

Research output: Contribution to journal › Article › peer-review

Abstract

We consider composite minimax optimization problems where the goal is to find a saddle-point of a large sum of non-bilinear objective functions augmented by simple composite regularizers for the primal and dual variables. For such problems, under the average-smoothness assumption, we propose accelerated stochastic variance-reduced algorithms with optimal up to logarithmic factors complexity bounds. In particular, we consider strongly-convex-strongly-concave, convex-strongly-concave, and convex-concave objectives. To the best of our knowledge, these are the first nearly-optimal algorithms for this setting.

Original language	English (US)
Pages (from-to)	100048
Journal	EURO Journal on Computational Optimization
Volume	10
DOIs	https://doi.org/10.1016/j.ejco.2022.100048
State	Published - Oct 18 2022

Bibliographical note

KAUST Repository Item: Exported on 2022-10-31
Acknowledgements: This work was supported by a grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier 000000D730321P5Q0002) and the agreement with the Moscow Institute of Physics and Technology dated November 1, 2021 No. 70-2021-00138.

Access to Document

10.1016/j.ejco.2022.100048

https://repository.kaust.edu.sa/bitstream/10754/685261/1/1-s2.0-S2192440622000247-main.pdf

Cite this

@article{5c28dda2095b487c967021b4d25746b3,

title = "Accelerated variance-reduced methods for saddle-point problems",

abstract = "We consider composite minimax optimization problems where the goal is to find a saddle-point of a large sum of non-bilinear objective functions augmented by simple composite regularizers for the primal and dual variables. For such problems, under the average-smoothness assumption, we propose accelerated stochastic variance-reduced algorithms with optimal up to logarithmic factors complexity bounds. In particular, we consider strongly-convex-strongly-concave, convex-strongly-concave, and convex-concave objectives. To the best of our knowledge, these are the first nearly-optimal algorithms for this setting.",

author = "Ekaterina Borodich and Vladislav Tominin and Yaroslav Tominin and Dmitry Kovalev and Alexander Gasnikov and Pavel Dvurechensky",

note = "KAUST Repository Item: Exported on 2022-10-31 Acknowledgements: This work was supported by a grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier 000000D730321P5Q0002) and the agreement with the Moscow Institute of Physics and Technology dated November 1, 2021 No. 70-2021-00138.",

year = "2022",

month = oct,

day = "18",

doi = "10.1016/j.ejco.2022.100048",

language = "English (US)",

volume = "10",

pages = "100048",

journal = "EURO Journal on Computational Optimization",

issn = "2192-4414",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Accelerated variance-reduced methods for saddle-point problems

AU - Borodich, Ekaterina

AU - Tominin, Vladislav

AU - Tominin, Yaroslav

AU - Kovalev, Dmitry

AU - Gasnikov, Alexander

AU - Dvurechensky, Pavel

N1 - KAUST Repository Item: Exported on 2022-10-31 Acknowledgements: This work was supported by a grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier 000000D730321P5Q0002) and the agreement with the Moscow Institute of Physics and Technology dated November 1, 2021 No. 70-2021-00138.

PY - 2022/10/18

Y1 - 2022/10/18

N2 - We consider composite minimax optimization problems where the goal is to find a saddle-point of a large sum of non-bilinear objective functions augmented by simple composite regularizers for the primal and dual variables. For such problems, under the average-smoothness assumption, we propose accelerated stochastic variance-reduced algorithms with optimal up to logarithmic factors complexity bounds. In particular, we consider strongly-convex-strongly-concave, convex-strongly-concave, and convex-concave objectives. To the best of our knowledge, these are the first nearly-optimal algorithms for this setting.

AB - We consider composite minimax optimization problems where the goal is to find a saddle-point of a large sum of non-bilinear objective functions augmented by simple composite regularizers for the primal and dual variables. For such problems, under the average-smoothness assumption, we propose accelerated stochastic variance-reduced algorithms with optimal up to logarithmic factors complexity bounds. In particular, we consider strongly-convex-strongly-concave, convex-strongly-concave, and convex-concave objectives. To the best of our knowledge, these are the first nearly-optimal algorithms for this setting.

UR - http://hdl.handle.net/10754/685261

UR - https://linkinghub.elsevier.com/retrieve/pii/S2192440622000247

UR - http://www.scopus.com/inward/record.url?scp=85140245874&partnerID=8YFLogxK

U2 - 10.1016/j.ejco.2022.100048

DO - 10.1016/j.ejco.2022.100048

M3 - Article

SN - 2192-4414

VL - 10

SP - 100048

JO - EURO Journal on Computational Optimization

JF - EURO Journal on Computational Optimization

ER -

Accelerated variance-reduced methods for saddle-point problems

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this