Parameter Free Decentralized Optimization

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2192 papers226 conceptsfrozen 2026-10-04

In the ideal vision of decentralized optimization, a swarm of autonomous agents—drones, sensors, or mobile devices—collaboratively solves a global problem using only local interactions. There is no central orchestrator, no master server, and no global clock.

However, a persistent "hidden" centralization haunts most classical algorithms. To guarantee stability and fast convergence, individual agents usually need to know global constants: the network's spectral gap (a measure of connectivity), the Lipschitz constant of the aggregate objective function, or even the total number of participants. In a truly dynamic or massive network, these values are impossible for a single node to observe.

Recent research is focused on closing this gap, moving toward "parameter-free" and "fully decentralized" methods that adapt to the environment without a bird's-eye view.

The Global Knowledge Barrier

To understand why this is a problem, consider the simple task of choosing a step size (learning rate). If the step size is too large, the system diverges; if it is too small, convergence takes forever. In decentralized settings, the "safe" step size is typically constrained by the worst-case connectivity of the entire graph.

As Cesar A. Uribe and Angelia Nedich demonstrate in Optimal Algorithms for Distributed Optimization, achieving optimal convergence rates requires a "network tax" proportional to the square root of the spectral gap. If an agent doesn't know this gap, it cannot set an optimal step size. This dependency, as noted by Alexandre Proutiere and Guodong Shi in Distributed Optimization: Convergence Conditions from a Dynamical System Perspective, forces agents to use overly conservative parameters, significantly hindering performance.

Gradient Tracking and Local Adaptation

A major breakthrough in bypassing global knowledge is Distributed Gradient Tracking (DGT). Instead of just averaging their local models, agents maintain an auxiliary variable to "track" the average gradient of the entire network.

Ying Sun shows in Decentralized Sparse Linear Regression via Gradient-Tracking that this mechanism allows a network to achieve the same linear convergence as a centralized solver, even in high-dimensional settings. By tracking the global gradient direction locally, agents become less sensitive to the specific nuances of the network topology.

Building on this, Farhad Farokhi and colleagues introduced Two-timescale EXTRA (TT-EXTRA) in Two-timescale EXTRA for Distributed Smooth Non-convex Optimization. By decoupling the primal and dual step sizes, they provide a more flexible framework that reduces the need for precise global tuning, especially for difficult non-convex objectives.

The most recent frontier is the development of truly parameter-free algorithms. These methods eliminate the need for pre-defined constants entirely by using local, adaptive mechanisms.

In Achieving Linear Convergence with Parameter-Free Algorithms in Decentralized Optimization, Alexander Gasnikov and Gesualdo Scutari propose a method that combines operator splitting with a local backtracking line-search. Instead of asking "what is the global Lipschitz constant?", each node asks "is my current step size working for my local function and my neighbors' current states?". This allows the algorithm to adaptively find the right pace for convergence without any prior knowledge of the network's spectral properties.

Self-Estimating Network Properties

If an algorithm absolutely must know a global property—like the number of nodes ($n$)—researchers are now building "plug-and-play" estimation layers. Seungjoon Lee describes a Fully Decentralized Design of Initialization-free Distributed Network Size Estimation that allows agents to reach a consensus on the total network size regardless of their initial state.

Similarly, in the realm of communication efficiency, Siva Theja Maguluri and Justin Romberg developed adaptive quantization schemes. These "zoom in" on the solution space, allowing nodes to communicate with high precision using only a few bits, effectively synchronizing the precision of communication with the progress of the optimization itself.

Why It Works: The Intuition of Local Correction

The core intuition behind this research direction is dynamic compensation. In older algorithms, errors caused by local-only information would accumulate, leading to "drift" or divergence. Modern parameter-free methods use feedback loops—like gradient tracking or adaptive step sizes—to treat these errors as signals.

When a node's local update moves too far from the group, the tracking variable or the line-search mechanism applies a "restoring force." By making these forces strong enough to overcome the lack of global knowledge, researchers like Na Li and Guannan Qu have shown that we can maintain grid stability or optimize complex functions using only local history and auxiliary variables, even when the global topology is a complete mystery to the individual agents.

Papers in this version

Showing 60 of 192 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 152 papers
  2. Version 1 · 2026-10-04 · 192 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_global_parameter_dependency_global_infor_d583d1d8,
  title = {global parameter dependency (global information dependency)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-parameter-dependency-global-information-dependency/rdr_d583d1d8320743058adf698a64167828},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_parameter_free_decentralized_optimizatio_d583d1d8_v1,
  title = {Parameter Free Decentralized Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parameter-free-decentralized-optimization/rdr_d583d1d8320743058adf698a64167828/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}