🔢 mathematics

Stochastic Mirror Descent under Iterate-Dependent Markov Noise: Analysis in the Asymptotic and Finite Time Regimes

This paper establishes a unified convergence framework for stochastic mirror descent under iterate-dependent Markov noise, proving almost sure convergence for both convex and non-convex problems and deriving finite-time sample complexity bounds that match classical rates in the convex setting.

Original authors: Anik Kumar Paul, Shalabh Bhatnagar

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anik Kumar Paul, Shalabh Bhatnagar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy valley (the optimization problem). You want to get to the bottom as quickly and safely as possible. In the world of computer science and math, this is called Stochastic Mirror Descent.

Usually, when you take a step, you ask a guide for directions. In standard scenarios, this guide is like a reliable friend who gives you a random but unbiased tip every time. However, this paper tackles a much trickier situation: The guide's mood and advice depend entirely on where you are standing right now.

Here is a breakdown of the paper's findings using simple analogies:

1. The Problem: The "Mood-Swing" Guide

In many real-world scenarios (like training an AI to play a game or managing a supply chain), the data you get isn't random in a vacuum. The data changes based on the decision you just made.

The Analogy: Imagine you are navigating a maze. In a normal maze, the walls stay put. But in this paper's maze, the walls move and shift depending on which direction you just turned. If you turn left, the path to the right might suddenly get blocked or change shape.
The Challenge: Because the "noise" (the shifting walls) depends on your current position, standard math tools that assume the noise is random and independent (like flipping a coin) break down. The guide is biased; they aren't just giving you random noise, they are giving you noise that is reactive to your choices.

2. The Solution: The "Mirror" Map

To handle this tricky, shifting terrain, the authors use an algorithm called Mirror Descent.

The Analogy: Standard navigation uses a flat map (Euclidean geometry). But if your terrain is curved or has weird shapes (like a probability distribution where you can't have negative numbers), a flat map is useless.
The Mirror: Think of "Mirror Descent" as using a special, curved mirror to view the world. This mirror warps the space so that the "straightest" path in the warped view corresponds to the best path in the real, curved world. It allows the algorithm to respect the rules of the game (like staying within a probability distribution) without getting stuck.

3. The Big Discovery: It Still Works!

The authors asked: "If the guide's advice depends on where we are, and the terrain is curved, will our algorithm actually find the bottom of the valley?"

They proved two main things:

A. The "Eventually" Guarantee (Asymptotic Convergence)

The Claim: If you keep walking long enough, you will almost certainly reach a stopping point where you can't go any lower.
The Catch: You don't need the terrain to be perfectly smooth (like a polished marble floor). It can be jagged and bumpy (non-smooth), as long as it doesn't have infinite cliffs (Lipschitz continuity).
The Metaphor: Even if the guide is fickle and the ground is rocky, if you keep taking small, careful steps, you will eventually stop moving because you've reached the bottom. This holds true whether the valley has one deep pit (convex) or many small dips and bumps (non-convex).

B. The "How Fast" Guarantee (Finite-Time Analysis)

The Claim: They also calculated exactly how many steps it takes to get close to the bottom with high confidence.
The Result:
- For Smooth, Simple Valleys (Convex): The speed is just as good as if the guide were a perfect, random coin-flipper. The "mood swings" of the guide didn't slow you down compared to the ideal scenario.
- For Bumpy, Complex Valleys (Non-Convex): They found a way to measure how close you are to the bottom using a special "Riemannian gradient" (a measure of steepness that fits the curved mirror). They proved that even in this messy, non-convex world, you can guarantee that you'll reach a "good enough" spot within a specific number of steps.

4. Why This Matters (According to the Paper)

The paper highlights that this is the first time anyone has proven these specific guarantees for this type of "reactive" noise in this specific "curved" setting.

Before: We knew how to navigate if the noise was random and independent, or if the noise depended on your position but the space was flat.
Now: We have a unified framework that handles both the reactive noise and the curved space simultaneously.

Summary

The paper says: "We have a new way to navigate a world where the rules change based on your moves. Even though the environment is tricky and the data is biased by your own actions, our 'Mirror' algorithm is robust enough to find the solution. It works for both simple and complex problems, and we can mathematically prove how long it will take to get there."

Note: The authors specifically mention that this setup appears in Reinforcement Learning, Controlled Markov Processes, and Performative Prediction. They do not claim this applies to medical treatments or clinical uses, but rather to these specific algorithmic and decision-making fields.

Technical Summary: Stochastic Mirror Descent Under Iterate-Dependent Markov Noise

Problem Formulation
This work addresses a stochastic optimization problem where the sampling distribution depends on the decision variable $x$ . The objective is to minimize:
$\min_{x \in \mathcal{X}} f(x) := \mathbb{E}_{s \sim \mu_x}[F(x, s)] = \int_S F(x, s) d\mu_x(s)$
where $\mathcal{X} \subseteq \mathbb{R}^d$ is a compact convex set. Unlike classical stochastic optimization where the distribution is fixed, here the probability measure $\mu_x$ varies with $x$ . This setting models decision-dependent uncertainty found in reinforcement learning, controlled Markov processes, and performative prediction.

A critical challenge in this setting is that direct sampling from $\mu_x$ is unavailable. Instead, for a given decision $x$ , samples are generated via an iterate-dependent Markov chain with transition kernel $\Pi(x, \cdot)$ and stationary distribution $\mu_x$ . This introduces two major complications:

Bias: The stochastic oracle is no longer unbiased in the classical sense because the distribution shifts with the iterate.
Temporal Dependence: The noise sequence is generated by a Markov process, rendering standard techniques for independent and identically distributed (i.i.d.) noise inapplicable.

Methodology and Algorithm
The authors propose and analyze the Stochastic Markov Mirror Descent (SMMD) algorithm. The update rule at iteration $n$ is given by:
$x_{n+1} = \arg\min_{x \in \mathcal{X}} \left\{ \langle g(x_n, S_n), x \rangle + \frac{1}{\alpha_n} D_R(x, x_n) \right\}$
where $g(x_n, S_n)$ is a stochastic subgradient, $\alpha_n$ is the step size, and $D_R$ is the Bregman divergence induced by a strongly convex mirror map $R$ . The state $S_n$ evolves according to the transition kernel $\Pi(x_n, S_n)$ .

The analysis relies on several key technical tools:

Stochastic Approximation with Markov Noise: The authors represent the discrete iterates as a stochastic approximation scheme. They derive an equivalent representation of the update involving a set-valued map $H_2$ that incorporates the stochastic subgradient, the normal cone of the constraint set, and higher-order error terms.
Dynamical Systems Approach: To establish convergence, the discrete process is interpolated into a continuous-time trajectory. The asymptotic behavior is characterized by the stability analysis of a differential inclusion driven by the Aumann integral of the set-valued subgradient mapping.
Poisson Equation Decomposition: For finite-time analysis, the Markov noise is decomposed using a Poisson equation associated with the Markov kernel. This separates the noise into a martingale difference term (which can be controlled via concentration inequalities) and a bias term that vanishes asymptotically.

Key Contributions and Results

Almost Sure Convergence (Convex and Non-Convex):
The paper establishes almost sure convergence of the SMMD iterates to the set of stationary points for both convex and non-convex objectives.
- Regularity: A significant contribution is that this result requires only Lipschitz continuity of the objective function. Differentiability is not assumed for the convergence proof, allowing the method to handle non-smooth problems.
- Framework: This is presented as the first analysis of a stochastic gradient-based method in the iterate-dependent Markov setting that handles non-convex and non-smooth objectives simultaneously.
Finite-Time Concentration Bounds (Smooth Objectives):
For smooth objectives, the authors derive finite-time concentration bounds.
- Convex Setting: The derived sample complexity matches the classical rate of stochastic mirror descent under i.i.d. noise. Specifically, the number of iterations required to achieve an $\epsilon$ -optimal solution with confidence $1-p$ scales as $\tilde{O}(1/\epsilon^2)$ .
- Non-Convex Setting: The authors derive a sample complexity bound in terms of the norm of the Riemannian gradient over the probability simplex. This metric, defined via the Hessian of the mirror map, is shown to be the appropriate measure of stationarity for constrained, non-Euclidean geometries. To the authors' knowledge, this is the first finite-time result for mirror descent in the presence of Markov noise, and potentially the first such result for mirror descent under i.i.d. noise in the constrained non-convex setting using this specific gradient norm.
Specific Analysis on the Probability Simplex:
In the context of the probability simplex (common in policy optimization), the authors utilize the negative entropy as the mirror map. They show that the tangent cone becomes a linear space in the relative interior, simplifying the projection operator. They prove that the mapping from the iterate to the projected descent direction is Lipschitz continuous, which is crucial for the finite-time bounds.

Significance and Claims
The paper claims to provide a unified convergence framework for stochastic mirror descent under state-dependent Markov noise. Its primary significance lies in bridging the gap between standard stochastic optimization (i.i.d. noise) and complex decision-dependent settings where the data distribution evolves with the algorithm's decisions.

The authors emphasize that their results extend existing literature in three specific ways:

They move beyond state-independent transition kernels (where the stationary distribution is fixed) to iterate-dependent kernels.
They provide almost sure convergence guarantees, which are stronger than the expected convergence ( $L_1$ or $L_2$ ) typically found in prior works on Markov noise.
They address non-smooth objectives in the almost sure convergence analysis, a feature often missing in Markov noise literature which typically assumes smoothness.

The work highlights that while the Markov noise introduces bias and temporal dependence, the Stochastic Mirror Descent algorithm remains robust, achieving convergence rates comparable to the i.i.d. case in the convex regime and providing rigorous finite-time guarantees for non-convex problems on the probability simplex.