论文标题
与马尔可夫数据一起适应随机优化的混合时间
Adapting to Mixing Time in Stochastic Optimization with Markovian Data
论文作者
论文摘要
我们考虑从马尔可夫链中绘制数据的随机优化问题。这种设置的现有方法至关重要地依赖于知道链的混合时间，而在现实世界中，通常未知。我们提出了不需要混合时间知识的第一种优化方法，但是当应用于凸问题时，可以获得最佳的渐近收敛速率。我们进一步表明，我们的方法可以扩展到：（i）通过马尔可夫数据找到非凸优化的固定点，以及（ii）在时间差异（TD）学习中更好地依赖对混合时间的依赖；在这两种情况下，我们的方法都完全忽略了混合时间。我们的方法依赖于多层蒙特卡洛（MLMC）梯度估计的新型组合以及一种自适应学习方法。
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 multi-level Monte Carlo (MLMC) gradient estimation together with an adaptive learning method.
