In traditional distributed optimization, we often assume that every participant in a network can solve their local portion of a problem perfectly before sharing the results. In a data center with high-speed interconnects and identical GPUs, this is a reasonable starting point. But in the "wild west" of Federated Learning—where models are trained on smartphones, IoT sensors, and edge devices—this assumption collapses.
Devices have varying battery levels, processing power, and network stability. Forcing a low-power sensor to solve a complex optimization subproblem to high precision is not just slow; it is often impossible. The research direction of Inexact Local Updates shifts the goal: instead of seeking perfect local solutions, we treat local computation as a tunable "inexact" step that provides just enough information to drive global convergence.
The Communication-Computation Tug-of-War
The fundamental bottleneck in distributed systems is communication. To reduce the number of times devices must talk to a central server, algorithms like FedAvg allow nodes to perform multiple local updates. However, as Reese Pathak and Martin J. Wainwright point out in FedSplit: an algorithmic framework for fast federated optimization, simply doing more local work can cause the global model to converge to the "wrong" solution if not handled carefully.
The solution is to formally treat these local updates as inexact proximal steps. In On the Convergence of Federated Optimization in Heterogeneous Networks, Anit Kumar Sahu and Tian Li demonstrate that the central server can safely aggregate results that have not reached full convergence, provided the local estimation error is bounded. This allows edge devices to perform only a few iterations of gradient descent rather than solving expensive sub-problems to high precision.
Stabilization and the Error Budget
If local updates are "noisy" approximations of the truth, how do we prevent the global model from drifting into chaos? The research points to two primary mechanisms: stabilization and error decay.
- Proximal Stabilization: Algorithms like S-DANE, developed by Xiaowen Jiang and Sebastian U. Stich in Stabilized Proximal-Point Methods for Federated Optimization, use an auxiliary sequence of "proximal centers." By decoupling the center of the optimization from the current global model, the algorithm stabilizes the updates. This ensures that even if a node provides a very coarse approximation, the global path remains on track.
- Managed Error Budgets: We can't be inexact forever. To reach an exact global optimum, the local "sloppiness" must decrease over time. Colin Jones and Ye Pu show in Inexact Alternating Minimization Algorithm for Distributed Optimization that if local errors decrease at a specific rate (proportional to the square of the iteration count), the global system maintains its convergence guarantees.
Solver-Agnostic Frameworks and Stragglers
One of the most practical benefits of this research is the ability to handle stragglers—nodes that are significantly slower than others. In the CoCoA framework, Virginia Smith and Martin Jaggi propose a solver-agnostic approach. Because the global framework is designed to tolerate inexactness, individual nodes can use any local solver—coordinate descent, Newton methods, or simple SGD.
This flexibility allows a system to manage heterogeneity dynamically. A powerful GPU node might solve its subproblem to high precision, while a mobile phone might only perform two steps of SGD. As long as the work meets a minimum "accuracy threshold," as explored by Grigory Malinovsky and Michal Grudzien in Can 5th Generation Local Training Methods Support Client Sampling?, the global model will converge.
Reaching the Theoretical Speed Limit
Can an "inexact" method ever be as fast as an "exact" one? Surprisingly, the answer is yes. By combining inexactness with acceleration techniques, researchers have closed the gap.
Sashank J. Reddi and Jakub Konečný introduced AIDE (Accelerated Inexact DanE), which uses a "Catalyst" framework to wrap inexact local solvers. This allows the algorithm to match the theoretical lower bounds for communication efficiency while using only first-order (gradient) information. Similarly, Eduard Gorbunov and Alexander Gasnikov demonstrate in Optimal Decentralized Distributed Algorithms for Stochastic Convex Optimization that inexact proximal steps can hit the speed limits for both communication rounds and local oracle calls.
Why It Works: The Intuition
The intuition behind inexact local updates is that global progress is limited by the slowest link. In a distributed network, the "slowest link" is usually the network itself. If the server is only going to update the global model once every ten minutes, there is no benefit to a client spending nine of those minutes refining a local solution to the 10th decimal place.
By allowing for inexactness, we reallocate the "computational budget" of the network. We accept a slightly "worse" update from each node in exchange for getting those updates much faster or from a much wider variety of devices. As long as the errors are managed through stabilization or decaying tolerances, the mathematical "gravity" of the global objective function eventually pulls all these approximate local steps toward the same optimal destination.