Distributed Gradient Tracking for Unbalanced Optimization With Different Constraint Sets

tracking methods have become popular for distributed optimization in recent years, partially because they achieve linear convergence using only a constant step-size for strongly convex optimization. In this article, we construct a counterexample on constrained optimization to show that direct extension of gradient tracking by using projections cannot guarantee the correctness. Then, we propose projected gradient tracking algorithms with diminishing step-sizes rather than a constant one for distributed strongly convex optimization with different constraint sets and unbalanced graphs. Our basic algorithm can achieve O(ln T/T ) convergence rate. Moreover, we design an epoch iteration scheme and improve the convergence rate as O(1/T ).

Automated summary

Tracking methods have gained popularity in distributed optimization, as they achieve linear convergence with a constant step-size for strongly convex optimization. This article presents a counterexample on constrained optimization, demonstrating that the direct extension of gradient tracking using projections cannot guarantee correctness. Instead, projected gradient tracking algorithms with diminishing step-sizes are proposed for distributed strongly convex optimization with different constraint sets and unbalanced graphs. The basic algorithm achieves an O(ln T/T) convergence rate, which is improved to O(1/T) with an epoch iteration scheme.