FedProx

The core innovation of FedProx is the addition of a proximal term to the local subproblem. Instead of minimizing the local empirical loss alone, each client minimizes h_k(w; w^t) = F_k(w) + (μ/2) ||w - w^t||².

• μ (mu): A tunable hyperparameter that controls the penalty for deviating from the global model w^t.
• Effect: This term restricts local updates from drifting too far when trained on highly skewed non-IID data, bounding the solution space.
• Benefit: Prevents the pathological divergence often seen in standard FedAvg when local datasets are statistically heterogeneous.

FedProx introduces a γ-inexactness condition to handle systems heterogeneity, specifically stragglers and partial participation. Instead of requiring clients to solve their local problems to a fixed precision, the framework allows for variable amounts of local computation.

• Mechanism: A client's local update w is accepted if ||∇h_k(w; w^t)|| ≤ γ_k ||∇h_k(w^t; w^t)||, where γ_k ∈ [0, 1].
• Straggler Mitigation: Slower clients can compute a less precise (higher γ) update and still contribute, rather than being dropped entirely.
• Convergence Guarantee: The method provides convergence guarantees that depend on the local inexactness, ensuring robustness to variable system performance.

FedProx is specifically designed to stabilize training across non-IID data partitions, a common failure mode for standard FedAvg.

• Client Drift Correction: The proximal term acts as a corrective force, pulling local models back toward the global consensus, mitigating the client drift caused by divergent local optima.
• Theoretical Foundation: The framework provides a convergence analysis that explicitly accounts for statistical dissimilarity across clients, offering a more realistic theoretical model than the IID assumption.
• Practical Impact: Empirically demonstrates more stable and faster convergence than FedAvg on heterogeneous partitions of standard vision and language datasets.

FedProx is a strict generalization of the standard Federated Averaging (FedAvg) algorithm, allowing practitioners to recover the baseline behavior seamlessly.

• μ = 0: Setting the proximal term coefficient to zero reduces the local objective to the standard empirical risk minimization used in FedAvg.
• γ = 0: Setting the inexactness parameter to zero requires clients to solve their local subproblem exactly, mirroring the standard assumption of full local epochs.
• Flexibility: This design allows for a smooth transition from standard FedAvg to the robust FedProx framework by simply tuning μ and γ, facilitating easy adoption in existing pipelines.

The foundational algorithm that FedProx generalizes. In FedAvg, clients perform multiple local stochastic gradient descent (SGD) steps before sending model updates to the server for weighted averaging. Unlike FedProx, FedAvg lacks a proximal term, making it vulnerable to client drift when local data distributions are non-IID. The server aggregates updates using a simple weighted average proportional to local dataset sizes.

An alternative algorithm that corrects for client drift using control variates. SCAFFOLD maintains a server-side control variate and client-side control variates that estimate the update direction of the global model. The difference between these variates is used to correct local updates, reducing variance caused by data heterogeneity. Unlike FedProx's proximal term, SCAFFOLD requires clients to maintain persistent state across rounds.

The defining mechanism of FedProx. A quadratic penalty is added to the local objective function that measures the Euclidean distance between the local model and the global model. The hyperparameter μ (mu) controls the strength of this regularization:

• μ = 0: Reduces to standard FedAvg
• μ > 0: Anchors local updates to the global model, limiting divergence
• Large μ: Increases convergence stability but may slow personalization

FedProx introduces the concept of γ-inexactness to accommodate heterogeneous system resources. Instead of requiring a fixed number of local epochs, clients can solve their local subproblems to varying degrees of accuracy based on available compute. A local update is γ-inexact if the gradient norm is bounded by γ times the gradient norm at the starting point. This provides a theoretical framework for straggler resilience without discarding partial work.

The primary challenge FedProx addresses. In real-world federated networks, client data distributions are non-IID (not independent and identically distributed). This causes local SGD updates to drift toward different local minima, slowing or preventing global convergence. FedProx's proximal term explicitly bounds this drift by penalizing the parameter divergence between local and global models, providing theoretical convergence guarantees under heterogeneous conditions.

A realistic federated learning scenario where only a subset of clients participate in each training round due to connectivity, battery, or availability constraints. FedProx provides theoretical convergence guarantees under partial participation, unlike standard FedAvg which assumes full or uniformly random participation. The proximal term stabilizes training when the active client set varies significantly between rounds, making it robust to real-world deployment conditions.