2025/07/31 by Kuruzov, Ilya, Chen, Xiaokai, Scutari, Gesualdo +1 · 3 citations
#FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2507.23725
We study decentralized optimization where multiple agents minimize the average of their (strongly) convex, smooth losses over a communication graph. Convergence of the existing decentralized methods generally hinges on an apriori, proper selection of the stepsize. Choosing this value is notoriously delicate: (i) it demands global knowledge from all the agents of the graph's connectivity and every local smoothness/strong-convexity constants--information they rarely have; (ii) even with perfect information, the worst-case tuning forces an overly small stepsize, slowing convergence in practice; and (iii) large-scale trial-and-error tuning is prohibitive. This work introduces a decentralized algorithm that is fully adaptive in the choice of the agents' stepsizes, without any global information and using only neighbor-to-neighbor communications--agents need not even know whether the problem is strongly convex. The algorithm retains strong guarantees: it converges at linear rate when the losses are strongly convex and at sublinear rate otherwise, matching the best-known rates of (nonadaptive) parameter-dependent methods.