In iterative optimization, a fundamental tension exists between how quickly an algorithm approaches a solution and how precisely it can settle upon it. This tension, often framed as the convergence-accuracy trade-off, centers on the selection of the step-size (or learning rate) and the penalty parameters that govern how agents in a system reach consensus.
Whether training a neural network, coordinating a swarm of robots, or performing distributed sensing, practitioners must choose between two regimes: a constant step-size that offers rapid progress but lingers in a "neighborhood" of the optimum, or a diminishing step-size that guarantees exactness at the cost of significant computational delays.
The Neighborhood of Constant Steps
When an algorithm uses a constant step-size, it maintains a consistent "momentum" toward the optimal solution. As Iiduka demonstrates in several works on fixed-point constraints, this approach allows for rapid convergence to an approximate solution. However, because the step-size never vanishes, the iterates eventually begin to oscillate or "bounce" within a bounded region around the true optimum.
This behavior is particularly visible in stochastic and distributed settings. Chen et al. note that in diffusion adaptation, the "error floor"—the residual distance to the true value—is directly proportional to the step-size. A larger step-size allows a network to track dynamic changes in data more agilely, but it forces the system to accept a higher steady-state error. As Koppel et al. argue, this creates a "proximity" rather than a "consensus," where agents stay close to the truth without ever perfectly resolving it.
The Precision of Diminishing Steps
To achieve exact convergence, the algorithm must eventually "cool down." By using a diminishing step-size—one that gradually reduces toward zero—the algorithm can suppress the noise and oscillations that plague constant-step methods. Iiduka shows that this is a requirement for ensuring that every cluster point of an optimization sequence is truly optimal.
The cost of this precision is time. Falsone et al. point out that vanishing step-sizes often lead to slow, logarithmic convergence rates. In reinforcement learning, Zhang et al. contrast the two: while constant steps yield exponential convergence to an error region, diminishing steps provide a much slower $O(1/T)$ rate toward the exact value. For many real-world applications, the time required to reach high-precision exactness is prohibitively long, leading researchers like Liu et al. to prioritize faster practical convergence over theoretical perfection.
The Penalty of Consensus
In distributed systems, the trade-off extends beyond the step-size to the way agents enforce agreement. To ensure all nodes in a network reach the same conclusion, researchers often use penalty functions or augmented Lagrangian methods.
The authors of IDEAL describe a "bottleneck" where increasing a regularization parameter accelerates the rate at which a network reaches consensus but simultaneously makes the local sub-problems harder to solve (ill-conditioning). Similarly, Wei et al. explain that in Newton-based distributed optimization, minimizing the residual error relative to the true optimum requires parameters that inherently degrade the efficiency of the optimization process.
Breaking the Trade-off
Recent advancements seek to bypass this dilemma by changing the fundamental mechanics of the update rule. A notable example is the EXTRA algorithm proposed by Shi et al.. While standard decentralized gradient descent is trapped in the speed-accuracy trade-off, the authors show that by utilizing the gradients of the two most recent iterates rather than just one, it is possible to achieve exact convergence while maintaining a fixed, large step-size.
This suggests that the trade-off is not an inescapable law of optimization, but rather a characteristic of first-order methods that rely on limited historical information. By incorporating more sophisticated tracking—such as the gradient tracking explored by Li et al.—researchers are beginning to develop algorithms that are both fast and exact.