Convex Minimization with Markov Noise
Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization with Markov Noise
We consider minimizing a differentiable convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and smoothness). The
function
Assumption 2 (Initial distance). There exists
Assumption 3 (Stationary Markov sampling and
mixing). The samples form a time-homogeneous Markov chain on
Assumption 4 (Stationary oracle moments). The map
Queries may be made at any point of
After the allotted calls, the output
Results
On a second-countable real Hilbert space with its Borel measurable
structure,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AcceleratedHeavyTailedMarkovConvex
(Ours) |
|||
| (2) Accelerated mirror descent with MLMC (Solodkin et al. 2025), Thm. 2, Cor. 2 | (1): Scope: stationary
|
(1): Hilbert geometry
only. On the geometric overlap, pays |
|
| (3) Ergodic mirror descent (Duchi et al. 2012), Thm. 1, (12); derived bound | (1): Scope: no bounded-gradient requirement; averaged rather than uniform mixing. Output: last accelerated iterate instead of averaging. | (1): Needs smoothness and
stationary start. For |
|
| (4) Accelerated stochastic proximal subgradient (He et al. 2026), Thm. 2(i), (7a) | (1): Scope: stationary
Markov dependence. Matches known i.i.d. rate when |
(1): Requires clipping; (4) does not. |
Abbr: