提出无需梯度的优化方法，高效应对马尔可夫噪声干扰。
Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity
- 用随机分批策略，避免依赖梯度信息
- 当混合时间τ小于维度d时，收敛速度与τ无关
- 适合高维、噪声复杂场景的优化问题
本文研究包含马尔可夫噪声的零阶优化问题。针对强凸光滑与非光滑情形，提出一种新型无梯度方法，支持单点和双点反馈。通过随机分批机制，证明当底层噪声序列的混合时间τ小于问题维度d时，该方法的收敛速率不依赖τ。这一发现表明：面对马尔可夫随机性，使用成本更低的零阶查询比昂贵的一阶信息更高效。最后，我们给出了对应的下界，验证了结果的最优性。
原文摘要 · Abstract (English)
This paper deals with stochastic optimization problems involving Markovian noise with a zero-order oracle. We present and analyze a novel derivative-free method for solving such problems in strongly convex smooth and non-smooth settings with both one-point and two-point feedback oracles. Using a randomized batching scheme, we show that when mixing time $τ$ of the underlying noise sequence is less than the dimension of the problem $d$, the convergence estimates of our method do not depend on $τ$. This observation provides an efficient way to interact with Markovian stochasticity: instead of invoking the expensive first-order oracle, one should use the zero-order oracle. Finally, we complement our upper bounds with the corresponding lower bounds. This confirms the optimality of our results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。