On Performance Guarantees for Federated Learning with Personalized Constraints

• URL: http://arxiv.org/abs/2603.19617v1
• Date: Fri, 20 Mar 2026 03:49:28 GMT
• Title: On Performance Guarantees for Federated Learning with Personalized Constraints
• Abstract summary: Federated learning (FL) has emerged as a communication-efficient algorithmic framework for distributed learning across multiple agents.<n>We propose PC-FedAvg, a method in which each agent maintains cross-estimates of the other agents' variables through a multi-block local decision vector.<n>We establish communication-complexity rates of $mathcalO(-2)$ for suboptimality and $mathcalO(-1)$ for agent-wise infeasibility.
• Score: 1.0195618602298684
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Federated learning (FL) has emerged as a communication-efficient algorithmic framework for distributed learning across multiple agents. While standard FL formulations capture unconstrained or globally constrained problems, many practical settings involve heterogeneous resource or model constraints, leading to optimization problems with agent-specific feasible sets. Here, we study a personalized constrained federated optimization problem in which each agent is associated with a convex local objective and a private constraint set. We propose PC-FedAvg, a method in which each agent maintains cross-estimates of the other agents' variables through a multi-block local decision vector. Each agent updates all blocks locally, penalizing infeasibility only in its own block. Moreover, the cross-estimate mechanism enables personalization without requiring consensus or sharing constraint information among agents. We establish communication-complexity rates of $\mathcal{O}(ε^{-2})$ for suboptimality and $\mathcal{O}(ε^{-1})$ for agent-wise infeasibility. Preliminary experiments on the MNIST and CIFAR-10 datasets validate our theoretical findings.

Related papers

• Decision-Focused Federated Learning Under Heterogeneous Objectives and Constraints [45.88028371034407]
  We build on the well-known SPO+ approach and develop heterogeneity bounds for the SPO+ surrogate loss.<n>In the case of strongly convex feasible regions, sharper bounds are derived due to the stability.<n>We implement a FedAvg-style DFFL set of experiments on both polyhedral and strongly convex problems.
  arXiv  Detail & Related papers  (2026-04-21T22:22:39Z)
• Adaptive Personalized Federated Learning via Multi-task Averaging of Kernel Mean Embeddings [16.820009380421368]
  Federated learning enables a collection of agents to collaboratively learn individual models without sharing raw data.<n>We propose a new PFL approach in which each agent optimize a weighted combination of all agents' empirical risks, with the weights learned from data rather than specified a priori.
  arXiv  Detail & Related papers  (2026-02-13T07:49:03Z)
• Distributed Online Convex Optimization with Nonseparable Costs and Constraints [7.671875264854638]
  We study a group of agents, networked via a communication graph, that collectively select actions to minimize a sequence of nonseparable global cost functions.<n>We propose a distributed online primal-dual belief consensus algorithm, where each agent maintains and updates a local belief of the global collective decisions.
  arXiv  Detail & Related papers  (2026-02-11T02:46:53Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Scalable Decentralized Algorithms for Online Personalized Mean Estimation [12.002609934938224]
  This study focuses on a simplified version of the overarching problem, where each agent collects samples from a real-valued distribution over time to estimate its mean.<n>We introduce two collaborative mean estimation algorithms: one draws inspiration from belief propagation, while the other employs a consensus-based approach.
  arXiv  Detail & Related papers  (2024-02-20T08:30:46Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees. We study this question in a general framework for interactive decision making with multiple agents. We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
  arXiv  Detail & Related papers  (2023-05-01T06:46:22Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints. We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates. The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
  arXiv  Detail & Related papers  (2022-09-16T09:38:38Z)
• Secure Distributed/Federated Learning: Prediction-Privacy Trade-Off for Multi-Agent System [4.190359509901197]
  In the big data era, performing inference within the distributed and federated learning (DL and FL) frameworks, the central server needs to process a large amount of data. Considering the decentralized computing topology, privacy has become a first-class concern. We study the textitprivacy-aware server to multi-agent assignment problem subject to information processing constraints associated with each agent.
  arXiv  Detail & Related papers  (2022-04-24T19:19:20Z)
• Distributed Adaptive Learning Under Communication Constraints [54.22472738551687]
  This work examines adaptive distributed learning strategies designed to operate under communication constraints. We consider a network of agents that must solve an online optimization problem from continual observation of streaming data.
  arXiv  Detail & Related papers  (2021-12-03T19:23:48Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  Decentralized multi-agent reinforcement learning algorithms are sometimes unpractical in complicated applications. We propose a flexible fully decentralized actor-critic MARL framework, which can handle large-scale general cooperative multi-agent setting. Our framework can achieve scalability and stability for large-scale environment and reduce information transmission.
  arXiv  Detail & Related papers  (2020-04-17T14:56:29Z)
• Dynamic Federated Learning [57.14673504239551]
  Federated learning has emerged as an umbrella term for centralized coordination strategies in multi-agent environments. We consider a federated learning model where at every iteration, a random subset of available agents perform local updates based on their data. Under a non-stationary random walk model on the true minimizer for the aggregate optimization problem, we establish that the performance of the architecture is determined by three factors, namely, the data variability at each agent, the model variability across all agents, and a tracking term that is inversely proportional to the learning rate of the algorithm.
  arXiv  Detail & Related papers  (2020-02-20T15:00:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.