A Locally Penalized Cross-Estimate Federated Method with Guarantees for Constrained Personalized Learning

Federated learning (FL) is a communication-efficient framework for solving distributed optimization problems. Standard FL methods aggregate local updates into a single global model that is shared by all agents, effectively imposing consensus. Under heterogeneous local constraints, however, a common feasible model may be overly restrictive or may not exist. Existing constrained FL methods largely retain this shared-model structure and therefore do not directly address personalization under heterogeneous agent-specific feasible sets. We study a constrained personalized FL problem that assigns a distinct feasible model to each agent while coupling the models through a collaborative objective. We propose Locally Penalized Cross-Estimate Federated Averaging (PCE-FedAvg), where each agent maintains a multi-block vector containing its own model and estimates of the other agents' models while applying the feasibility penalty only locally to its own block. The server aggregates corresponding blocks separately, thereby preserving personalization without requiring agents to explicitly disclose their local constraint sets. For any ε>0, we establish finite-time upper and lower suboptimality bounds and agent-wise squared infeasibility bounds, yielding communication complexities of O(ε^{-2}) and O(ε^{-1}), respectively. Experiments on MNIST and CIFAR-10 support our theoretical results.