SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2202.04428 · ICML · 2022

Adapting to Mixing Time in Stochastic Optimization with Markovian Data

Kfir Levy, Ron Dorfman

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

We consider stochastic optimization problems where data is drawn from a Markov chain. Existing methods for this setting crucially rely on knowing the mixing time of the chain, which in real-world applications is usually unknown. We propose the first optimization method that does not require the knowledge of the mixing time, yet obtains the optimal asymptotic convergence rate when applied to convex problems. We further show that our approach can be extended to: (i) finding stationary points in non-convex optimization with Markovian data, and (ii) obtaining better dependence on the mixing time in temporal difference (TD) learning; in both cases, our method is completely oblivious to the mixing time. Our method relies on a novel combination of multilevel Monte Carlo (MLMC) gradient estimation together with an adaptive learning method.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2202.04428")
get_code_for_paper("2202.04428")
have("2202.04428")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2202.04428.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2202.04428.svg)](https://syntology.ai/paper/2202.04428)

Connect an agent — have() is free.