In decentralized optimization, a network of independent agents collaborates to minimize a global objective function without a central coordinator. Traditionally, ensuring that these agents converge to a consensus requires a delicate balancing act. To guarantee stability, standard algorithms rely heavily on global network parameters—such as the graph's spectral gap (the second smallest eigenvalue of the Laplacian matrix) or global Lipschitz smoothness constants.
As highlighted by Yazdandoost Hamedani et al. in their work on time-varying networks, requiring agents to know these global parameters prevents the deployment of true "plug-and-play" systems. If the network topology changes dynamically, or if a single node is added, the global constants shift, forcing a manual recalculation of hyperparameters across the entire network. Furthermore, forcing every node to adopt a conservative, globally safe stepsize creates a performance bottleneck where the entire network is dragged down to the speed of its slowest or worst-connected component, a limitation addressed by the authors of TriPD.
The Core Intuition: Decoupling Local and Global Dynamics
How can nodes optimize effectively if they don't know the layout of the network they inhabit? The key insight behind parameter-free decentralized optimization is that local function curvature and immediate neighborhood interactions provide enough signal to guide convergence. Instead of scaling updates based on global network topology, agents can dynamically compute independent stepsizes using purely local information.
Xu et al. demonstrated in a unified contraction analysis that optimal stepsizes can be determined using only the smoothness and convexity parameters of local objective functions, mirroring centralized gradient descent. By basing parameters strictly on local Lipschitz constants, agents decouple their stepsize selection from the network's spectral gap entirely. Similarly, Vogels et al. showed in their study on communication compression that decentralized consensus can be stabilized without manual hyperparameter tuning by decoupling communication compression levels from the underlying optimization rate, allowing standard centralized learning rates to be applied directly in decentralized environments.
Mechanisms of Local Autonomy
To achieve this parameter independence, several algorithmic mechanisms have emerged to replace global constants with local, adaptive checks.
Local Backtracking Line-Search
Rather than using a fixed stepsize, nodes can run localized line-searches to adaptively find the largest permissible stepsize at each iteration. Gasnikov et al. introduced a variable metric framework in their paper on linear convergence that allows agents to evaluate stepsizes based on local function curvature rather than global connectivity. Xiaokai Chen et al. proved in a composite convex optimization framework that these local backtracking procedures are mathematically sufficient to guarantee convergence, requiring information only from immediate neighbors and the node's own loss function. To handle ill-conditioned problems, Schwager et al. extended this to a fully decentralized line-search within a distributed Quasi-Newton framework, enabling nodes to estimate system curvature locally.
Adaptive Stepsizes and Gradient Tracking
For stochastic or non-convex settings where line-search is computationally expensive, algorithms rely on adaptive rules. Lou et al. introduced adaptive stepsize rules in switching communication environments that allow agents to dynamically learn adjustment rates based on local information, facilitating complex tasks like distributed Nash equilibrium computation.
In non-convex stochastic optimization, Li Jiaxiang et al. combined gradient normalization with moving-average tracking in D-NASA to eliminate the need for prior knowledge of smoothness constants or network connectivity. This tracking philosophy is also mirrored in bilevel optimization; Zhai et al. leveraged adaptive stepsizes and gradient-norm tracking in AdaSDBO to eliminate manual hyperparameter tuning while maintaining optimal convergence speeds.
Self-Tuning Weights and Penalties
Beyond stepsizes, other optimization parameters can be automated locally. Early work by Aritra Ghosh 0001 et al. showed in their analysis of gossip algorithms that networks could execute decentralized subgradient methods to self-tune their own communication weights without global topology data. In the context of the Alternating Direction Method of Multipliers (ADMM), Song et al. demonstrated in their fast ADMM variant that nodes can autonomously adjust penalty parameters by comparing the performance of neighbor models against local data, eliminating manual configuration and reducing sensitivity to initial setups.
Why Local Autonomy Guarantees Global Convergence
It might seem counterintuitive that a network of agents, each changing its stepsize independently based on local conditions, can reach a coherent global consensus. If Node A takes massive steps because its local function is flat, while Node B takes tiny steps because its local landscape is highly curved, won't they pull the system apart?
The reason it works lies in the mathematical decoupling of local optimization steps from the consensus mechanism. By utilizing frameworks like variable metrics (Gasnikov et al.) or block-specific steplengths (Lei et al. in their asynchronous variance-reduced schemes), the algorithms ensure that local step variations are absorbed into the agent's internal state updates without distorting the communication weights that bind the network together.
Furthermore, as shown by Wei et al. in the context of Network Newton methods, distributed stepsize selection criteria can determine update magnitudes without needing the global optimal function value, achieving superlinear convergence rates in expectation. Because these algorithms bound the local stepsizes based on local smoothness, they guarantee that no single node oversteps to the point of divergence, allowing the network to automatically find the optimal global solution at a centralized-equivalent rate.
Key Foundational Work
A symmetric adaptive algorithm for speeding-up consensus (2010) — contributed 1 concept elements to this direction.
Gossip algorithms: design, analysis and applications (2005) — contributed 1 concept elements to this direction.