A Parameter-free Decentralized Algorithm for Composite Convex Optimization

The paper studies decentralized optimization over networks, where agents minimize a composite objective consisting of the sum of smooth convex functions–the agents’ losses–and an additional nonsmooth convex extended value function. We propose a decentralized algorithm wherein agents $adaptively$ adjust their stepsize using local backtracking procedures that require $no$ $global$ (network) information or extensive inter-agent communications. Our adaptive decentralized method enjoys robust convergence guarantees, outperforming existing decentralized methods, which are not adaptive. Our design is centered on a three-operator splitting, applied to a reformulation of the optimization problem. This reformulation utilizes a proposed BCV metric, which facilitates decentralized implementation and local stepsize adjustments while guarantying convergence.