CISPA
Browse
cispa_all_3801.pdf (929.74 kB)

Decentralized Local Stochastic Extra-Gradient for Variational Inequalities

Download (929.74 kB)
Version 2 2023-12-14, 12:33
Version 1 2023-11-29, 18:22
conference contribution
posted on 2023-12-14, 12:33 authored by Aleksandr Beznosikov, Pavel Dvurechensky, Anastasia Koloskova, Valentin Samokhin, Alexander Gasnikov, Sebastian StichSebastian Stich
We consider distributed stochastic variational inequalities (VIs) on unbounded domains with the problem data that is heterogeneous (non-IID) and distributed across many devices. We make a very general assumption on the computational network that, in particular, covers the settings of fully decentralized calculations with time-varying networks and centralized topologies commonly used in Federated Learning. Moreover, multiple local updates on the workers can be made for reducing the communication frequency between workers. We extend the stochastic extragradient method to this very general setting and theoretically analyze its convergence rate in the strongly monotone, monotone, and non-monotone settings when a Minty solution exists. The provided rates explicitly exhibit the dependence on network characteristics (e.g., mixing time), iteration counter, data heterogeneity, variance, number of devices, and other standard parameters. As a special case, our method and analysis apply to distributed stochastic saddle-point problems (SPP), e.g., to training Deep Generative Adversarial Networks (GANs) for which decentralized training has been reported to be extremely challenging. In experiments for decentralized training of GANs we demonstrate the effectiveness of our proposed approach.

History

Preferred Citation

Aleksandr Beznosikov, Pavel Dvurechensky, Anastasia Koloskova, Valentin Samokhin, Sebastian Stich and Alexander Gasnikov. Decentralized Local Stochastic Extra-Gradient for Variational Inequalities. In: Conference on Neural Information Processing Systems (NeurIPS). 2022.

Primary Research Area

  • Trustworthy Information Processing

Name of Conference

Conference on Neural Information Processing Systems (NeurIPS)

Legacy Posted Date

2022-10-12

Open Access Type

  • Green

BibTeX

@inproceedings{cispa_all_3801, title = "Decentralized Local Stochastic Extra-Gradient for Variational Inequalities", author = "Beznosikov, Aleksandr and Dvurechensky, Pavel and Koloskova, Anastasia and Samokhin, Valentin and Stich, Sebastian U. and Gasnikov, Alexander", booktitle="{Conference on Neural Information Processing Systems (NeurIPS)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC