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 (Objective and initial distance). The
function
Assumption 2 (Stationary Markov sampling and
mixing). Let
Assumption 3 (Stationary oracle moments). The map
Queries may be made at any point of
Results
- Stretched Exponential Markov Convex Lower Bound · Lean proof
- Stretched Exponential Markov Convex Upper Bound · Lean proof
Convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) StretchedExponentialMarkovConvexLowerBound
(Ours) |
|||
| (2) StretchedExponentialMarkovConvexUpperBound (Ours) (review) | |||
| (3) (LongTails, n.d.), specialized polynomial-mixing guarantee | (2): Matches known rate, algorithm and output; identical budget under the envelope inclusion. | (2): Finite-dimensional, noise-dominated specialization of a Hilbert-space guarantee. | |
| (4) (Solodkin et al. 2025), Thm. 2/Cor. 2 | Expected total cost: Special case: |
(2): Scope: stationary
|
(2): Euclidean geometry only. |
| (5) Derived bound, (Duchi et al. 2012), Thm. 1/(12) | Special case: convex sample losses, |
(2): Matches the |
(2): Needs smoothness and a stationary start; Euclidean geometry only. |
Abbr: