FedPCD: Priority-Constrained Federated Aggregation

The gist: FedPCD introduces a priority-constrained federated optimization framework that separates global federated aggregation from client protection, preserving the conventional aggregate as primary while allowing only minimal correction to satisfy client performance constraints.

How it works

FedPCD is based on Priority-Constrained Descent (PCD), which is a hierarchical multi-objective optimization framework that distinguishes a primary objective from secondary objectives and seeks the smallest deviation from the primary descent direction required to guarantee progress on secondary objectives The server seeks a direction that remains as close as possible to the FedAvg update while satisfying the prescribed client-level requirements, introducing the minimum correction necessary to satisfy the violated constraints If the FedAvg direction already satisfies these requirements, FedPCD leaves it unchanged.

The framework converts the client update displacement into a local pseudo-gradient and forms a primary FedPCD direction by aggregating these using the same weights as FedAvg to create a FedAvg-like descent direction. This is then normalized, and the constrained problem is solved to find the direction that remains closest to the current federated aggregate while satisfying client-level progress requirements. The final update direction is rescaled using the norm of the current aggregate, ensuring the magnitude of the update remains tied to the federated aggregate.

Key Components and Mechanisms

The framework incorporates several mechanisms to handle real-world FL challenges:

1. Priority Constraint Formulation: It treats the conventional federated aggregate as the primary objective and individual client updates as secondary constraints, allowing only for the minimum deviation required to satisfy these constraints.

2. Partial Participation Handling: To address partial participation, FedPCD incorporates a client-history mechanism that retains recently observed client directions to increase representation. This history window stores the pseudo-gradient of each client that participated within the window.

3. Convergence Analysis: Under deterministic full participation, FedPCD establishes an O(1/T) convergence rate for the round-averaged squared l2-norm of the global gradient. Furthermore, it demonstrates convergence to simultaneous client stationarity under the stated geometric conditions.

Experimental Results and Performance

Extensive experiments across CIFAR-10, CIFAR-100, and Fashion-MNIST under 2 levels of participation and 3 data heterogeneity levels show superior performance compared to 10 tested fairness-aware FL baselines. FedPCD consistently achieves the highest global accuracy in all cases and the highest worst-10% accuracy in 17 of 18 tested configurations.

The framework demonstrates significant empirical communication efficiency gains, reaching FedAvg’s final accuracy using only 10%–44% of the total communication rounds and achieving the strongest baseline’s final accuracy earlier in 16 of 18 configurations.

Theoretical Guarantees

The theoretical analysis establishes a finite-time convergence rate for FedPCD under certain assumptions, proving that after T communication rounds, the bound on the global objective decrease is proportional to O(1/T). Corollary 4.2 further proves Composite Multi-Stationarity (CMS), which is stronger than Pareto stationarity because it requires every client gradient to be zero individually.

The analysis also confirms that the uniform alignment condition prevents this cancellation from invalidating the client-gradient bound along the analyzed trajectory and that CMS is conditional on that geometry, not a consequence of smoothness.

Ablation Studies

Component ablation studies confirm the importance of each part of the framework; removing history reduces performance because the history mechanism has the largest effect, particularly under stronger heterogeneity. Setting τ = 0 consistently reduces performance relative to the complete method, showing that enforcing positive client progress provides an additional benefit beyond the history mechanism itself. Instantaneous l2 normalization achieves the best global accuracy at all heterogeneity levels, although EMA normalization with β = 0.8 slightly improves client standard deviation in one specific setting.

This work presents FedPCD, a priority-constrained federated optimization framework that separates global federated aggregation from client protection, preserving the conventional aggregate as primary while allowing only minimal correction to satisfy client performance constraints. This research is important because it provides a method that balances global model utility with individual client progress requirements, leading to superior accuracy and faster convergence in federated learning settings.

--- Page 1 ---

FedPCD: Priority-Constrained Federated Aggregation

Yousef Irshaid1, Dara Varam1, Mohamed I. AlHajri1 mialhajri@aus.edu Department of Computer Science & Engineering, American University of Sharjah 2 Senseable City Laboratory, Massachusetts Institute of Technology Equal contribution.

Abstract Federated learning (FL) seeks to optimize a shared global model from decentralized client data while keeping their data decentralized (McMahan et al., 2017; Kairouz et al., 2021). Standard federated averaging (FedAvg) constructs a global update by aggregating the locally trained model updates of participating clients (McMahan et al., 2017). However, client data distributions are commonly heterogeneous (Li et al., 2020b; Karimireddy et al., 2020), and when local data distributions differ, the resulting direction can make substantial progress for some clients while providing little, none or even adverse progress for others (Wang et al., 2021; Hu et al., 2022; Pan et al., 2023). This motivates performance fairness in FL, in which the goal is to improve the uniformity of client-level performance while maintaining the utility of the global model (Li et al., 2019; Shi et al., 2024). A substantial body of work has consequently modified the optimization objective to improve client-level fairness Shi et al. (2024). Among the earliest works, Agnostic FL (AFL) formulates a minimax objective over mixtures of client distributions and optimizes it by adaptively updating the mixture weights according to their losses (Mohri et al., 2019). Similarly, q-Fair FL (q-FFL) modifies the objective to place greater emphasis on clients with higher losses (Li et al., 2019). Other approaches formulate federated learning as a multiobjective optimization problem, treating client losses as separate objectives and seeking an update direction that provides simultaneous progress across clients (Hu et al., 2022; Pan et al., 2023; 2024). Gradient-conflictbased methods similarly modify the aggregated direction when client updates are incompatible (Wang et al., 2017). Despite their different formulations, these methods share the broader goal of modifying the global optimization process to account for client-level objectives rather than aggregate performance alone.

--- Page 2 ---

Multi-objective approaches are of particular relevance to our approach because they treat client losses as separate objectives and seek a common descent direction that improves the objectives of all participating clients These methods typically seek convergence to a Pareto-stationary solution, at which no direction exists that can simultaneously decrease all client objectives to first order (Hu et al., 2022). While this provides a principled way to account for client-level progress, the client objectives are treated symmetrically when constructing the global update. In standard FL, however, the FedAvg direction already represents the update preferred by the shared global objective. Replacing this direction may be unnecessary when it already provides sufficient progress for the individual client objectives. This idea motivates FedPCD, a federated adaptation of Priority-Constrained Descent (PCD) (Varam & Alhajri, 2026). PCD is a hierarchical multi-objective optimization framework that distinguishes a primary objective from secondary objectives and seeks the smallest deviation from the primary descent direction required to guarantee progress on secondary objectives. In FedPCD, the FedAvg update assumes the primary role, while individual client update directions define secondary constraints <ref:2610.

1. Improved AI systems can achieve superior global accuracy while maintaining better worst-10% client performance across heterogeneous data distributions by using FedPCD, which consistently outperforms state-of-the-art baselines, achieving the highest global accuracy across all configurations and leading worst-10% client accuracy in nearly all.

2. Improved communication efficiency can be realized by utilizing FedPCD to reach final performance levels substantially faster, as it demonstrates faster empirical convergence, reaching matching or superior performance in substantially fewer communication rounds, potentially saving 10%–44% of the total communication rounds compared to FedAvg.

3. The system can better handle sparse and partial client participation by incorporating a client-history mechanism that retains recently observed client directions to increase representation, ensuring that even infrequent clients contribute meaningfully to the optimization process under conditions where updates are intermittent.

4. The optimization framework can be designed to balance global objective progress with individual constraints by treating the conventional federated aggregate as the primary objective while applying only the minimum correction necessary to meet client performance constraints, thereby avoiding changes that change the global optimization direction or treat client objectives symmetrically.

5. The system's convergence properties can be analyzed to establish a strong theoretical guarantee, specifically demonstrating an O(1/T) convergence rate for the round-averaged squared l2-norm of the global gradient under deterministic full participation, leading to simultaneous client stationarity under geometric conditions.