论文标题
在不平衡的网络中分发在线优化，没有明确的亚级别
Distributed Online Optimization in Time-Varying Unbalanced Networks without Explicit Subgradients
论文作者
论文摘要
本文研究了在没有明确亚级别的情况下，通过在线变化不平衡的挖掘图上进行了分布的在线约束优化问题。与现有算法形成鲜明对比的是，我们设计了一种基于局部随机的零级甲骨文的新型基于共识的在线分布式算法，然后通过构造行列式矩阵来重新销售甲骨文，旨在解决时间变化的图形的不平衡。在温和的条件下，只要累积变化以特定顺序增长，平均动态遗憾以均衡速率渐近地表明会渐近地收敛。此外，还提供了可用的亚级别时，还提供了拟议算法的对应物，以及其动态遗憾的界限，这反映了我们算法的收敛基本上不受零好的oracle的影响。使用传感器网络中的分布式目标跟踪问题和动态稀疏信号恢复问题的仿真来证明所提出的算法的有效性。
This paper studies a distributed online constrained optimization problem over time-varying unbalanced digraphs without explicit subgradients. In sharp contrast to the existing algorithms, we design a novel consensus-based distributed online algorithm with a local randomized zeroth-order oracle and then rescale the oracle by constructing row-stochastic matrices, which aims to address the unbalancedness of time-varying digraphs. Under mild conditions, the average dynamic regret over a time horizon is shown to asymptotically converge at a sublinear rate provided that the accumulated variation grows sublinearly with a specific order. Moreover, the counterpart of the proposed algorithm when subgradients are available is also provided, along with its dynamic regret bound, which reflects that the convergence of our algorithm is essentially not affected by the zeroth-order oracle. Simulations on distributed targets tracking problem and dynamic sparse signal recovery problem in sensor networks are employed to demonstrate the effectiveness of the proposed algorithm.
