Methods for Solving Variational Inequalities with Markovian Stochasticity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910222738522112 |
|---|---|
| author | Solodkin, Vladimir Ermoshin, Michael Gavrilenko, Roman Beznosikov, Aleksandr |
| author_facet | Solodkin, Vladimir Ermoshin, Michael Gavrilenko, Roman Beznosikov, Aleksandr |
| contents | In this paper, we present a novel stochastic method for solving variational inequalities (VI) in the context of Markovian noise. By leveraging Extragradient technique, we can productively solve VI optimization problems characterized by Markovian dynamics. We demonstrate the efficacy of proposed method through rigorous theoretical analysis, proving convergence under quite mild assumptions of $L$-Lipschitzness, strong monotonicity of the operator and boundness of the noise only at the optimum. In order to gain further insight into the nature of Markov processes, we conduct the experiments to investigate the impact of the mixing time parameter on the convergence of the algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_13428 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Methods for Solving Variational Inequalities with Markovian Stochasticity Solodkin, Vladimir Ermoshin, Michael Gavrilenko, Roman Beznosikov, Aleksandr Optimization and Control In this paper, we present a novel stochastic method for solving variational inequalities (VI) in the context of Markovian noise. By leveraging Extragradient technique, we can productively solve VI optimization problems characterized by Markovian dynamics. We demonstrate the efficacy of proposed method through rigorous theoretical analysis, proving convergence under quite mild assumptions of $L$-Lipschitzness, strong monotonicity of the operator and boundness of the noise only at the optimum. In order to gain further insight into the nature of Markov processes, we conduct the experiments to investigate the impact of the mixing time parameter on the convergence of the algorithm. |
| title | Methods for Solving Variational Inequalities with Markovian Stochasticity |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2409.13428 |