{"ID":2888470,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.23725","arxiv_id":"2507.23725","title":"Adaptive Stepsize Selection in Decentralized Convex Optimization","abstract":"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 \\emph{linear} rate when the losses are strongly convex and at \\emph{sublinear} rate otherwise, matching the best-known rates of (nonadaptive) parameter-dependent methods.","short_abstract":"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 dem...","url_abs":"https://arxiv.org/abs/2507.23725","url_pdf":"https://arxiv.org/pdf/2507.23725v1","authors":"[\"Ilya Kuruzov\",\"Xiaokai Chen\",\"Gesualdo Scutari\",\"Alexander Gasnikov\"]","published":"2025-07-31T16:58:40Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}