In large-scale machine learning, the network is almost always the bottleneck. Spreading a massive dataset across thousands of GPUs or edge devices allows for immense parallel computing power, but coordinating those devices requires constant communication.
Traditional distributed optimization frameworks analyze this communication overhead through a pessimistic lens. They assume worst-case data heterogeneity, meaning the loss function on one machine could look entirely different from the loss function on another. To guarantee convergence under these assumptions, algorithms must bound their step sizes and communication frequencies using a global smoothness constant ($L$). As Szlendak et al. point out, this reliance on a global constant fails to reflect the actual similarity of data across different machines, preventing algorithms from achieving the faster training speeds that are possible when workers possess homogeneous datasets.
In reality, distributed data is rarely adversarial; it is often statistically similar. Whether because nodes sample from the same underlying data distribution or because modern over-parameterized models naturally interpolate data, local objective functions tend to share significant structural homogeneity. A rapidly growing body of research exploits this function similarity to bypass traditional communication bottlenecks, fundamentally shifting how we design and analyze distributed optimization algorithms.
The Core Intuition: Isolating the Variance
Why does function similarity allow us to communicate less?
Imagine two nodes trying to cooperatively find the minimum of a global function. If their local datasets are identical, their local gradients will always point in the exact same direction. They would never need to communicate until the very end of training. If their datasets are slightly different, their gradients will drift apart, but only gradually.
Instead of treating each local function as completely independent, similarity-aware algorithms reformulate the optimization objective to isolate the difference (or variance) between local and global functions. As Kovalev et al. demonstrate, this strategy allows communication rounds to be scaled based on the degree of similarity between nodes rather than the total smoothness of the global objective. If the local functions are highly similar, the variance term changes slowly, meaning the system only needs to synchronize when these differences become significant.
Pessimistic Framework:
[Node 1 (Worst-Case Heterogeneity)] <--- Frequent Sync (Bounded by Global L) ---> [Node 2]
Similarity-Aware Framework:
[Node 1] ---\
+---> [Isolate Variance / Quantify Closeness (δ)] <--- Infrequent Sync (Bounded by δ)
[Node 2] ---/
By replacing global smoothness constants with local similarity parameters in complexity analysis, algorithms can drastically reduce the number of required communication rounds. Tian et al. show that this shift allows decentralized optimization to scale with a relative condition number rather than a global one. Crucially, as the volume of data per node increases, the statistical similarity between local datasets typically improves. This creates an inverse relationship between data size and communication cost: similarity-based algorithms naturally become more communication-efficient as the problem scales.
Quantifying Similarity: First and Second Order
To exploit function similarity algorithmically, researchers must mathematically quantify how "close" local functions are to one another. This is primarily done in two ways:
First-Order Similarity (Gradient Closeness)
First-order approaches measure how much local gradients deviate from the global average gradient. For instance, Gruntkowska et al. utilize a framework that quantifies similarity by measuring the variance of local gradients relative to the global average. This metric serves as a quantifiable resource, allowing optimization algorithms to adaptively compress communication or adjust synchronization frequencies based on the real-time homogeneity of the system.
Second-Order Similarity (Hessian Closeness)
Second-order approaches look at the curvature of the functions, measuring the distance between local Hessians and the global Hessian. Lin et al. leverage average second-order similarity to develop "smoothness-free" distributed algorithms. Because these methods do not rely on global smoothness constants, they achieve faster convergence in scenarios where global variation is massive but the local variation between nodes is small. Similarly, Jiang et al. show that exploiting second-order similarity allows federated learning systems to automatically scale their performance based on data homogeneity, achieving state-of-the-art communication efficiency while lowering local processing requirements.
Algorithmic Mechanisms for Exploitation
Several distinct algorithmic paradigms have emerged to translate function similarity into communication savings.
Gradient Sliding
Gradient sliding algorithms decouple local computation from communication. In standard distributed gradient descent, every local gradient computation must be followed by a communication round. Under function similarity, algorithms can perform multiple local computational steps (sliding) before synchronizing. Kovalev et al. applied this to distributed systems to hit theoretical lower bounds for both communication and computation simultaneously. Extending this to non-smooth, non-differentiable objectives, Zhang et al. proved that deterministic algorithms can achieve a direct linear dependency between communication rounds and the degree of function similarity.
Local Surrogates and Proximal Proxies
Another powerful mechanism involves using a local function as a proxy for the global objective. In the SONATA framework proposed by Sun et al., agents construct sophisticated local "surrogate" functions that go beyond simple linear approximations, allowing for highly effective local updates when data is statistically similar.
In centralized master-worker setups, this concept manifests as a proximal-like reformulation. As explored by Beznosikov et al., the central server can perform the primary computational tasks using its own local data, while distributed nodes merely provide small, corrective updates. Because of high data similarity, the server's local function acts as an incredibly accurate proxy for the global state, minimizing the need for heavy bidirectional communication.
Broadening the Paradigm
The benefits of exploiting function similarity extend far beyond standard convex optimization.
- Saddle-Point and Minimax Problems: In complex environments like Generative Adversarial Networks (GANs) or adversarial training, optimization involves finding a saddle point. Beznosikov et al. and Zhou et al. demonstrated that shifting dependency from global smoothness to local similarity metrics tightens complexity bounds and slashes communication overhead for distributed minimax problems.
- Variational Inequalities: By combining data similarity with communication compression and local steps, the "Three Pillars" algorithm developed by Beznosikov et al. achieved state-of-the-art communication complexity for distributed variational inequalities.
- Client Selection in Federated Learning: In practical federated settings, full synchronization is impossible, requiring partial client sampling. Jiang et al. showed that gradient estimators can be explicitly designed to exploit functional similarity between client distributions, maintaining high convergence rates even when only a fraction of clients are sampled.
- Over-Parameterized Models: For modern deep learning models that can perfectly fit training data (interpolation), Qin et al. demonstrated that even minimal data similarity can eliminate the traditional performance penalty associated with performing many local updates, transitioning the system away from a convergence rate limited by local drift.
Ultimately, treating data similarity as a quantifiable resource transforms distributed optimization. Instead of forcing algorithms to prepare for worst-case data divergence, modern frameworks adapt to the underlying homogeneity of the data, unlocking faster training speeds and drastically reducing network strain.
Key Foundational Work
Distributed Saddle-Point Problems Under Data Similarity (2021) — contributed 5 concept elements to this direction.
Optimal Gradient Sliding and its Application to Optimal Distributed Optimization Under Similarity (2022) — contributed 3 concept elements to this direction.
Acceleration in Distributed Optimization under Similarity (2022) — contributed 3 concept elements to this direction.