论文标题
用分布式随机梯度跟踪技术的零级单点估计
Zero-Order One-Point Estimate with Distributed Stochastic Gradient-Tracking Technique
论文作者
论文摘要
在这项工作中，我们考虑了一个分布式的多代理随机优化问题，在该问题中，每个代理都具有光滑且凸的局部目标函数，并且要经过随机过程。目的是让所有代理人合作找到一种通用解决方案，以优化这些本地功能的总和。通过一个实际的假设，即代理只能一次只能获得嘈杂的数值函数查询，我们将分布式随机梯度跟踪方法扩展到没有梯度估计的强盗设置，并且我们引入了零订单（ZO）（ZO）单点估计值（1P-DSGT）。我们使用随机近似工具分析了这种新技术的收敛，以进行平滑和凸的目标，并证明它几乎可以肯定地达到最佳。然后，我们研究目标何时进一步强烈凸的收敛速率。在足够数量的迭代$ k> k_2 $之后，我们获得了$ o（\ frac {1} {\ sqrt {k}}）$的速率，通常对于使用单点估计器的技术是最佳的。我们还提供了$ o（\ sqrt {k}）$的遗憾，与上述技术相比，这非常好。我们进一步说明了使用数值实验提出的技术的有用性。
In this work, we consider a distributed multi-agent stochastic optimization problem, where each agent holds a local objective function that is smooth and convex, and that is subject to a stochastic process. The goal is for all agents to collaborate to find a common solution that optimizes the sum of these local functions. With the practical assumption that agents can only obtain noisy numerical function queries at exactly one point at a time, we extend the distributed stochastic gradient-tracking method to the bandit setting where we don't have an estimate of the gradient, and we introduce a zero-order (ZO) one-point estimate (1P-DSGT). We analyze the convergence of this novel technique for smooth and convex objectives using stochastic approximation tools, and we prove that it converges almost surely to the optimum. We then study the convergence rate for when the objectives are additionally strongly convex. We obtain a rate of $O(\frac{1}{\sqrt{k}})$ after a sufficient number of iterations $k > K_2$ which is usually optimal for techniques utilizing one-point estimators. We also provide a regret bound of $O(\sqrt{k})$, which is exceptionally good compared to the aforementioned techniques. We further illustrate the usefulness of the proposed technique using numerical experiments.
