Review for NeurIPS paper: Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization

Summary and Contributions: The paper considers smooth and strongly-convex decentralized optimization problems. The authors propose a novel primal gossip-based optimization algorithm (OPAPC) which is provably optimal w.r.t. Existing optimal algorithms for this setting rely on access to dual gradient which, in absence of any structure, can be very expensive. The suggested method uses primal (1st order) access exclusively---forming the main contribution of the paper. The main algorithmic idea is to use a generalized forward backward-like algorithm with the corresponding positive-definite operator being chosen according to the gossip matrix (so as to comply with the underlying decentralized structure).