# Methods for Optimization Problems with Markovian Stochasticity and Non-Euclidean Geometry

arXiv: https://arxiv.org/abs/2408.01848 · HTML: https://mlsanity.com/paper/2408.01848/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Aug 2024.

## Built on by (most cited first, 2 of 2)

- [Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity](https://mlsanity.com/paper/2601.01160/) (2026)
- [Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization](https://mlsanity.com/paper/2607.25785/) (2026)

## Abstract (arXiv)

This paper examines a variety of classical optimization problems, including well-known minimization tasks and more general variational inequalities. We consider a stochastic formulation of these problems, and unlike most previous work, we take into account the complex Markov nature of the noise. We also consider the geometry of the problem in an arbitrary non-Euclidean setting, and propose four methods based on the Mirror Descent iteration technique. Theoretical analysis is provided for smooth and convex minimization problems and variational inequalities with Lipschitz and monotone operators. The convergence guarantees obtained are optimal for first-order stochastic methods, as evidenced by the lower bound estimates provided in this paper.