Coordination on a Budget: Federated Active Learning with Few Labels

# Coordination on a Budget: Federated Active Learning with Few Labels
Source: [https://arxiv.org/html/2608.18634](https://arxiv.org/html/2608.18634)
Daphna WeinshallAffiliation:School of Computer Science and EngineeringAffiliation:The Hebrew University of Jerusalem, Jerusalem 91904, IsraelEmail:[\{liam\.mohr,daphna\}@mail\.huji\.ac\.il](mailto:)

Abstract

Federated Active Learning \(FAL\) addresses the dual challenges of data privacy and label scarcity, where the absence of a global data view introduces additional hurdles for coordinated query selection\. We study cross\-silo FAL in the low\-budget regime, where annotation decisions are most critical\. We characterize, both theoretically and empirically, a*heterogeneity reversal*: in low\-budget settings, homogeneous \(IID\) data requires stronger coordination to avoid redundant queries, whereas heterogeneous data naturally promotes diversity; this trend reverses at higher budgets\. Thus, in contrast to the standard federated learning \(FL\) narrative where heterogeneity is a primary challenge, we show that IID settings are more challenging for query selection in FAL\.

Motivated by these findings, we propose a new FAL framework that utilizes federated representation learning to align client data in a shared embedding space\. This enables the server to perform globally coordinated active selection over optionally obfuscated client embeddings, while annotation remains local to each client\. Although our framework operates in the more challenging low\-budget regime, it achieves performance that surpasses existing FAL methods even when they are given substantially larger annotation budgets, demonstrating the value of centralized coordination under privacy constraints\.

## 1Introduction

Modern machine learning systems are increasingly deployed in settings where data is decentralized and subject to strict privacy and governance constraints\. In domains such as healthcare, finance, and telecommunications, data is distributed across institutions and cannot be shared due to regulatory or operational limitations\. Federated Learning \(FL\) addresses this challenge by enabling collaborative model training without access to raw data\. However, FL typically assumes labeled data, while in practice, unlabeled data is abundant and annotations are costly and scarce\.

Active Learning \(AL\) offers a complementary solution by selectively querying the most informative samples for annotation\. Yet, classical AL relies on centralized access to the unlabeled pool, allowing the model to compare candidates globally\. In federated settings, this assumption breaks down: data remains distributed across clients, and coordination is restricted by privacy and communication constraints\. This gives rise to the setting of*Federated Active Learning*\(FAL\), where query selection must be performed without direct access to a global data view\.

A central challenge in FAL is coordinating selection across clients to avoid redundant or suboptimal queries\. While data heterogeneity is traditionally viewed as a primary obstacle in federated learning, we uncover a contrasting phenomenon in the low\-budget regime\. Specifically, we observe a*heterogeneity reversal*: when clients have similar \(IID\) data distributions, independent selection leads to redundant queries and poor global coverage, making coordination essential\. In contrast, heterogeneous \(non\-IID\) data naturally promotes diversity in selected samples, reducing the need for coordination\. This trend reverses at higher budgets, where non\-IID data introduces bias in uncertainty estimation, reverting to the classical challenges of FL\. We formalize this interaction in Section[3](https://arxiv.org/html/2608.18634#S3), showing that the value of coordination depends jointly on data heterogeneity and labeling budget\. Table[1](https://arxiv.org/html/2608.18634#S1.T1)summarizes the resulting reversal between diversity\- and uncertainty\-driven regimes\.

![Refer to caption](https://arxiv.org/arxiv/extracted/7968011/images/method_visualization.png)Figure 1:Overview of the proposed federated active learning pipeline\. A federated feature extractor first induces a shared embedding space across clients\. Each client then computes local embeddings and may apply an obfuscation mechanism before transmitting them to the server\. The server performs centralized active selection in the aggregated embedding space, while the selected samples are labeled locally by the corresponding clients and used for subsequent federated training\.Table 1:Coordination vs\. heterogeneity\.In the low\-budget regime, IID data require coordination to ensure diversity, making them more challenging than non\-IID data \- a reversal of the standard FL setting\.Our analysis reveals a key limitation of existing FAL approaches: they do not explicitly account for the interaction between data distribution and labeling budget\. A natural baseline is to apply active learning independently at each client and rely on federated training only after annotation, as in prior low\-budget FAL pipelines\[ono2025exploring\]\. However, this confines inter\-client coordination to the model\-training stage, leaving query selection decoupled across clients and failing to fully exploit the potential synergy between active learning and federated learning\.

We address this limitation through globally coordinated query selection in a shared federated representation space\. A federatively learned feature extractor aligns client embeddings, allowing the server to compare candidates across clients and coordinate selection while raw data remain local\. Selected samples are then labeled locally and used for downstream federated training \(see Figure[1](https://arxiv.org/html/2608.18634#S1.F1)\)\.

While this design enables effective coordination across clients, it also introduces a potential privacy risk, as shared embeddings may leak information about the underlying data; in visual domains, feature representations can be vulnerable to inversion or reconstruction attacks\[chatzikokolakis2013broadening,feyisetan2020privacy,sun2021soteria\]\. To address this challenge, we investigate two privacy\-preserving approaches, using either controlled perturbation of embeddings or centroid\-based aggregation, and study the resulting trade\-offs between privacy protection and active selection performance\.

##### Our contributions are:

- •We identify and analyze a*heterogeneity reversal*in federated active learning: in low\-budget regimes, IID data leads to redundant sampling and requires stronger coordination than heterogeneous data\.
- •We propose a new framework for*globally coordinated query selection*using shared federated embedding, with two differential\-privacy mechanisms for data protection\.
- •We show that global coordination substantially improves label efficiency in the low\-budget regime, while retaining much of this advantage under embedding obfuscation, yielding a favorable privacy\-performance trade\-off\.

## 2Related Work

##### Low\-Budget Active Learning\.

Early in the AL process, uncertainty\-based methods, such as Entropy Sampling\[wang2014new\], Least Confidence\[lewis1994sequential\], and Margin Sampling\[scheffer2001active\], frequently underperform because the model’s predictive signal is of low quality\[hacohen2022active\]\. To mitigate this, recent approaches leverage self\-supervised representations\. For instance,*TypiClust*\[hacohen2022active\]prioritizes representative samples from high\-density clusters\. Similarly,*ProbCover*\[yehuda2022active\]and*MaxHerding*\[bae2024maxherding\]frame active selection as a probabilistic coverage problem, strategically picking samples to maximize the probability that the unlabeled data manifold is spanned within the given budget constraint\.

##### Federated Learning\.

Federated learning \(FL\) enables collaborative model training across distributed clients while keeping data localized, primarily addressing privacy, communication efficiency, and statistical heterogeneity\[mcmahan2017communication,kairouz2021advances\]\. A large body of work focuses on mitigating the challenges arising from non\-IID data distributions and limited communication bandwidth\[li2020federated,karimireddy2020scaffold\]\.

In contrast, our work considers a small number of clients with relatively homogeneous data distributions, allowing us to isolate a different bottleneck: labeled\-data scarcity and its interaction with distributed active selection\. This perspective complements existing FL research by highlighting challenges that arise even when communication constraints and data heterogeneity are less pronounced\.

##### Federated contrastive representation learning\.

Methods that are effective for federated learning under supervised objectives, such as cross\-entropy, are significantly less effective for contrastive learning, since the global self\-supervised objective does not decompose into a sum of local objectives\[zhuang2021divergence\]\. This mismatch can lead to degraded representations when applying standard federated averaging\. Prior work has proposed adaptations such as prototype\-based alignment or modified contrastive objectives to mitigate this issue\[ye2021fedproto,li2021federatedcontrastive\]\. Much work has been dedicated to address the adversarial effect of non\-IID client distribution on FCRL\[dong2021federated,zhuang2021divergence,jing2024fedsc,han2022fedx,seo2024relaxed,louizosmutual\]\. Contrastive learning under differential privacy was likewise explored, as in\[li2022dpcl\]\.

##### Federated Active Learning\.

Most federated active learning \(FAL\) methods rely on model\-based scoring to estimate sample informativeness, making them effective primarily in high\-budget regimes while degrading at low budgets\. Early work such as\[ahmed2020active\]adopts a*separate*AL \(S\-AL\) paradigm, where selection is performed locally at each client\. In contrast, F\-AL\[ahn2024federated\]enables collaborative evaluation but shows clear gains only at higher budgets \(e\.g\., 150–200 labels per class on CIFAR\-100\)\. Others address this mismatch by selecting samples informative for both local and global objectives\[kim2022lg,cao2023knowledge,kim2023re\], typically focusing on non\-IID settings where heterogeneity complicates uncertainty estimation\[zhang2023affectfal\]\. Finally, in Active Federated Learning \(AFL\), the decision concerns*which clients*to train rather than which samples to label\[goetz2019active\]\.

To the best of our knowledge, the only FAL method that remains effective in the low\-budget regime is\[ono2025exploring\]\. This approach follows a separate active learning \(S\-AL\) paradigm, where sample evaluation is performed locally at each client\. By leveraging a selection criterion tailored to low\-budget settings\[hacohen2022active\], it performs well in federated scenarios and outperforms existing FAL baselines\[ono2025exploring\]\. We therefore adopt it as a primary baseline in our experiments\.

## 3Heterogeneity & Inter\-Client Coordination

Standard active learning balances two criteria:diversity, which promotes coverage of the feature space, anduncertainty, which targets low\-confidence regions\. In federated settings, the value of inter\-client coordination depends critically on data heterogeneity\. We analyze this interaction in the context of active learning query selection criteria, and highlight two key effects:

1. 1\.Diversity\-centric selection:Under IID data, independent clients tend to select overlapping samples, requiring strong coordination to avoid redundancy\. In contrast, heterogeneous data naturally partitions the space, reducing the need for coordination\.
2. 2\.Uncertainty\-centric selection:Under IID data, independent clients tend to learn similar models\. In contrast, under non\-IID data, local models become biased estimators of global uncertainty, making coordination necessary\. This aligns with classical FL results\[mcmahan2017communication\], where heterogeneity induces model divergence\.

Together, these effects reveal a*reversed vulnerability*in Federated Active Learning: coordination is most critical for diversity under*IID data*, and for uncertainty under*non\-IID data*\. We formalize this relationship in Section[3\.2](https://arxiv.org/html/2608.18634#S3.SS2), focusing on the diversity regime where this reversal departs from standard FL, and validate it empirically in Sections[5\.2](https://arxiv.org/html/2608.18634#S5.SS2)and[5\.4](https://arxiv.org/html/2608.18634#S5.SS4), with detailed results provided in Appendix[C](https://arxiv.org/html/2608.18634#A3)\.

### 3\.1Notation and Preliminaries

Let𝒳⊆ℝd\\mathcal\{X\}\\subseteq\\mathbb\{R\}^\{d\}denote the feature space and𝒴\\mathcal\{Y\}the label space\. ConsiderKKclients, where clientk∈\{1,…,K\}k\\in\\\{1,\\ldots,K\\\}possesses a local data distribution𝒫k\\mathcal\{P\}\_\{k\}over𝒳×𝒴\\mathcal\{X\}\\times\\mathcal\{Y\}\. Let

𝒳k=supp⁡\(𝒫kX\)\\mathcal\{X\}\_\{k\}=\\operatorname\{supp\}\(\\mathcal\{P\}\_\{k\}^\{X\}\)denote the support of the feature marginal of clientkk\.

###### Definition 1\(Coordination Gap\)\.

LetΦ⁡\(S\)\\Phi\(S\)denote a selection utility for a setS⊆𝒳S\\subseteq\\mathcal\{X\}\. Letbkb\_\{k\}denote the annotation budget of clientkk, with

∑k=1Kbk=B\.\\sum\_\{k=1\}^\{K\}b\_\{k\}=B\.Define the optimal coordinated utility as

ΦB⋆=maxSk⊆𝒳k,\|Sk\|=bkk=1,…,K⁡Φ⁡\(⋃k=1KSk\)\.\\Phi\_\{B\}^\{\\star\}=\\max\_\{\\begin\{subarray\}\{c\}S\_\{k\}\\subseteq\\mathcal\{X\}\_\{k\},\\ \|S\_\{k\}\|=b\_\{k\}\\\\ k=1,\\ldots,K\\end\{subarray\}\}\\Phi\\left\(\\bigcup\_\{k=1\}^\{K\}S\_\{k\}\\right\)\.For each client, let

Sk⋆∈arg⁡maxS⊆𝒳k\|S\|=bk⁡Φ⁡\(S\)S\_\{k\}^\{\\star\}\\in\\arg\\max\_\{\\begin\{subarray\}\{c\}S\\subseteq\\mathcal\{X\}\_\{k\}\\\\ \|S\|=b\_\{k\}\\end\{subarray\}\}\\Phi\(S\)denote its locally optimal selection\. The coordination gap is

ΔK=ΦB⋆−Φ⁡\(⋃k=1KSk⋆\)\.\\Delta\_\{K\}=\\Phi\_\{B\}^\{\\star\}\-\\Phi\\left\(\\bigcup\_\{k=1\}^\{K\}S\_\{k\}^\{\\star\}\\right\)\.\(1\)

### 3\.2Data Heterogeneity and Diversity

We show that the utility of coordination increases with overlap between clients’ selections and vanishes when heterogeneity separates their accessible regions\. We formalize this relationship using a cell\-coverage model\.

Let the shared embedding space be partitioned intoMMcells,𝒞=\{C1,…,CM\},\\mathcal\{C\}=\\\{C\_\{1\},\\ldots,C\_\{M\}\\\},representing regions such as clusters or high\-density neighborhoods\. Define the coverage utility

Φ\(S\)=∑m=1M𝟏\{S∩Cm≠∅\}\.\\Phi\(S\)=\\sum\_\{m=1\}^\{M\}\\mathbf\{1\}\\\{S\\cap C\_\{m\}\\neq\\emptyset\\\}\.\(2\)For each client, define the accessible cell set

Ak=\{m:Cm∩𝒳k≠∅\},A\_\{k\}=\\\{m:C\_\{m\}\\cap\\mathcal\{X\}\_\{k\}\\neq\\emptyset\\\},\(3\)and the cell\-selection probability

ak,m=Pr⁡\(Sk⋆∩Cm≠∅\)\.a\_\{k,m\}=\\Pr\(S\_\{k\}^\{\\star\}\\cap C\_\{m\}\\neq\\emptyset\)\.\(4\)Thus,ak,m=0a\_\{k,m\}=0wheneverm∉Akm\\notin A\_\{k\}\.

We start from the expected coordination gapΔ¯K\\bar\{\\Delta\}\_\{K\}:

Δ¯K\\displaystyle\\bar\{\\Delta\}\_\{K\}=\\displaystyle=𝔼⁡\[ΔK\]=𝔼⁡\[ΦB⋆\]−𝔼⁡\[Φ⁡\(⋃k=1KSk⋆\)\]\\displaystyle\\mathbb\{E\}\[\\Delta\_\{K\}\]=\\mathbb\{E\}\[\\Phi\_\{B\}^\{\\star\}\]\-\\mathbb\{E\}\[\\Phi\(\{\\bigcup\_\{k=1\}^\{K\}S\_\{k\}^\{\\star\}\}\)\]\(5\)=\\displaystyle=𝔼⁡\[ΦB⋆\]−∑k=1K𝔼⁡\[Φ⁡\(Sk⋆\)\]\\displaystyle\\mathbb\{E\}\[\\Phi\_\{B\}^\{\\star\}\]\-\\sum\_\{k=1\}^\{K\}\\mathbb\{E\}\[\\Phi\(S\_\{k\}^\{\\star\}\)\]\+∑k=1K𝔼\[Φ\(Sk⋆\)\]−𝔼\[Φ\(⋃k=1KSk⋆\)\]\\displaystyle\+\\sum\_\{k=1\}^\{K\}\\mathbb\{E\}\[\\Phi\(S\_\{k\}^\{\\star\}\)\]\-\\mathbb\{E\}\[\\Phi\(\{\\bigcup\_\{k=1\}^\{K\}S\_\{k\}^\{\\star\}\}\)\]\(6\)
The expression in \([5](https://arxiv.org/html/2608.18634#S3.E5)\) captures the difference between the objectives optimized by the two methods\. In the very low\-budget regime, we assume that each selection \- whether local or global \- is efficient, selecting at most one point per cell\. Thus, uncoordinated but efficient selection yields𝔼⁡\[ΦB⋆\]≈∑k=1K𝔼⁡\[Φ⁡\(Sk⋆\)\]\\mathbb\{E\}\[\\Phi\_\{B\}^\{\\star\}\]\\approx\\sum\_\{k=1\}^\{K\}\\mathbb\{E\}\[\\Phi\(S\_\{k\}^\{\\star\}\)\]\(see Appendix[F](https://arxiv.org/html/2608.18634#A6)\)\.

The key difference therefore lies in \([6](https://arxiv.org/html/2608.18634#S3.E6)\), which measures how much of the utility independently gained by individual clients is preserved in the combined selected set rather than lost to redundant selections\. We thus focus on the*expected redundancy gap*Δ¯Kred\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}, defined as

Δ¯Kred=∑k=1K𝔼⁡\[Φ⁡\(Sk⋆\)\]−𝔼⁡\[Φ⁡\(⋃k=1KSk⋆\)\]\.\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=\\sum\_\{k=1\}^\{K\}\\mathbb\{E\}\[\\Phi\(S\_\{k\}^\{\\star\}\)\]\-\\mathbb\{E\}\\\!\\left\[\\Phi\\\!\\left\(\\bigcup\_\{k=1\}^\{K\}S\_\{k\}^\{\\star\}\\right\)\\right\]\.\(7\)Under the aforementioned efficient\-selection assumption,

Δ¯K≈Δ¯Kred\.\\bar\{\\Delta\}\_\{K\}\\approx\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}\.\(8\)Thus, in what follows, we focus on the redundancy gap\.

###### Proposition 1\(Heterogeneity and the Redundancy Gap\)\.

Assume that, for each cellCmC\_\{m\}, the events\{Sk⋆∩Cm≠∅\}\\\{S\_\{k\}^\{\\star\}\\cap C\_\{m\}\\neq\\emptyset\\\}are independent across clients\. Then the following hold:

1. 1\.If the accessible cell sets are pairwise disjoint, Ai∩Aj=∅∀i≠j,A\_\{i\}\\cap A\_\{j\}=\\emptyset\\qquad\\forall i\\neq j,then Δ¯Kred=0\.\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=0\.
2. 2\.Define the contribution of cellCmC\_\{m\}to the expected redundancy gap as Δm=∑k=1Kak,m−\(1−∏k=1K\(1−ak,m\)\)\.\\Delta\_\{m\}=\\sum\_\{k=1\}^\{K\}a\_\{k,m\}\-\\left\(1\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)\\right\)\.Then ∂Δm∂aj,m=1−∏k≠j\(1−ak,m\)≥0,\\frac\{\\partial\\Delta\_\{m\}\}\{\\partial a\_\{j,m\}\}=1\-\\prod\_\{k\\neq j\}\(1\-a\_\{k,m\}\)\\geq 0,with strict inequality whenever another client selects fromCmC\_\{m\}with positive probability\.
3. 3\.Let cm\(K\)=1−∏k=1K\(1−ak,m\)c\_\{m\}^\{\(K\)\}=1\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)be the probability that at least one of the firstKKclients selects fromCmC\_\{m\}\. Then Δ¯K\+1red−Δ¯Kred=∑m=1MaK\+1,m​cm\(K\)\.\\bar\{\\Delta\}\_\{K\+1\}^\{\\mathrm\{red\}\}\-\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=\\sum\_\{m=1\}^\{M\}a\_\{K\+1,m\}c\_\{m\}^\{\(K\)\}\.

Proof is provide in Appendix[F\.3](https://arxiv.org/html/2608.18634#A6.SS3)\.

The last result shows that the marginal redundancy introduced by an additional client is determined by its overlap with the existing selection profile\. Heterogeneity that shifts selection mass toward cells with smallcm\(K\)c\_\{m\}^\{\(K\)\}therefore causes a smaller increase in the*redundancy gap*\.

###### Corollary 1\.

If the clients’ distributions are IID, the*redundancy gap*increases \(or remains unchanged\) with the number of clients\.

###### Proof\.

If all clients have identical cell\-level selection probabilitiesa1,m=⋯=aK,m=ama\_\{1,m\}=\\cdots=a\_\{K,m\}=a\_\{m\}, then

Δ¯Kred=∑m=1M\[K​am−\(1−\(1−am\)K\)\],\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=\\sum\_\{m=1\}^\{M\}\\left\[Ka\_\{m\}\-\\left\(1\-\(1\-a\_\{m\}\)^\{K\}\\right\)\\right\],\(9\)and

Δ¯K\+1red−Δ¯Kred=∑m=1Mam​\[1−\(1−am\)K\]≥0\.\\bar\{\\Delta\}\_\{K\+1\}^\{\\mathrm\{red\}\}\-\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=\\sum\_\{m=1\}^\{M\}a\_\{m\}\\left\[1\-\(1\-a\_\{m\}\)^\{K\}\\right\]\\geq 0\.\(10\)∎

###### Corollary 2\.

Adding a client whose accessible cells do not overlap with those of the existing clients introduces no additional redundancy\.

###### Proof\.

AK\+1∩⋃k=1KAk=∅⟹Δ¯K\+1red−Δ¯Kred=0\.A\_\{K\+1\}\\cap\\bigcup\_\{k=1\}^\{K\}A\_\{k\}=\\emptyset~~\\implies~~\\bar\{\\Delta\}\_\{K\+1\}^\{\\mathrm\{red\}\}\-\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=0\.∎

Together, these results explain why homogeneous partitions may require stronger coordination than heterogeneous partitions: IID clients repeatedly spend their budgets on similar regions, whereas heterogeneity naturally reduces duplicated coverage\.

###### Observation 1\.

The theoretical coordination gap in Eq\. \([1](https://arxiv.org/html/2608.18634#S3.E1)\) is nonnegative because it is defined relative to the centralized optimum\. The empirical gap between realizable centralized and local selection methods may nevertheless be negative\. This can occur when a non\-IID partition reveals semantic structure that is not fully represented by the embedding geometry, allowing independent local selection to outperform the centralized selection method \(see Figure[6\(b\)](https://arxiv.org/html/2608.18634#S5.F6.sf2)\)\.

## 4Method

We propose a three\-phase FAL framework for cross\-silo settings111While ’cross\-silo’ more precisely describes our setting, we henceforth use ’client’ to align with prevailing FL nomenclature\.: \(i\) federated representation learning, \(ii\) privacy\-conscious centralized active selection under client\-level budgets, and \(iii\) federated downstream training \(Figure[1](https://arxiv.org/html/2608.18634#S1.F1)\)\. Raw data remain local throughout; only perturbed representations or their obfuscated summaries are communicated for query coordination\.

### 4\.1Three\-Phase Pipeline

##### Phase I: Federated Representation Learning

The first phase \(Figure[1](https://arxiv.org/html/2608.18634#S1.F1), highlighted in teal\) constructs a shared representation space across clients, enabling coordination during the subsequent active selection stage\. Accordingly, we train a shared feature extractor using standard Federated Learning \(FL\), adopting FedAvg\[mcmahan2017communication\]to train a SimCLR encoder in a federated manner \(see Section[2](https://arxiv.org/html/2608.18634#S2)\)\. At each communication round, the server broadcasts the current encoder, clients perform local contrastive learning on their unlabeled data, and the server aggregates the resulting updates\. This allows clients to collaboratively learn a common representation without exchanging raw data\. Once training is complete, the global encoder is frozen and distributed to all clients, which use it to embed their local unlabeled data\.

##### Phase II: Obfuscated Centralized Active Selection

The second phase \(Figure[1](https://arxiv.org/html/2608.18634#S1.F1), highlighted purple\) performs centralized active query selection over the clients’ unlabeled data\. To this end we adopt three methods that have demonstrated superior performance in the low\-budget regime \-*ProbCover*\[yehuda2022active\],*TypiClust*\[hacohen2022active\]and*MaxHerding*\[bae2024maxherding\], adapted to the current setting by adding local client budget constraints\.

#### Client\-Constrained Selection

We apply centralized AL selection globally in the shared embedding space while enforcing client\-level annotation budgets\. For ProbCover and MaxHerding, the server greedily selects the feasible sample with the largest marginal coverage gain, excluding samples from clients whose budgets have been exhausted\. For TypiClust, clustering is performed globally, and cluster representatives are allocated subject to the same client budgets\. The formal objective, greedy procedure, and approximation guarantee are provided in Appendix[B](https://arxiv.org/html/2608.18634#A2)\.

#### Obfuscation

Directly transmitting embeddings may still introduce privacy risks, including reconstruction or inversion attacks\. We therefore study two approaches for obfuscating the per\-client embeddings before they are used for centralized selection\. Both approaches aim to preserve enough geometric information for effective selection, while reducing the amount of information exposed to the server\.

##### Approach 1: using controlled perturbation\.

##### Approach 2: using data aggregates\.

We follow the principle of geometric summarization\[ye2021fedproto, e\.g\.,\], whereby clients communicate only aggregate geometric information rather than individual embeddings\. To enable coordinated active selection under this constraint, we introduce federated adaptations of ProbCover and TypiClust in Section[4\.2](https://arxiv.org/html/2608.18634#S4.SS2)\.

##### Phase III: Federated Training of a Global Classifier

In Phase III \(Figure[1](https://arxiv.org/html/2608.18634#S1.F1), highlighted blue\) selected samples remain local and are used for federated downstream training\. We evaluate a neural network trained on raw images, and as an effective alternative in low budgets, a shallow classifier trained over the shared representation learned in Phase I\.

### 4\.2Aggregate\-Based Federated Active Selection

Sharing individual embeddings enables global coordination, but may reveal information about individual samples\. We therefore introduce two federated adaptations of geometry\-based active learning,*FederatedProbCover*and*FederatedTypiClust*, that coordinate selection across clients while communicating only geometric aggregates and distances\. Unlike independent client selection, these methods recover the global geometric information needed for coordinated querying without exposing individual embeddings\.

##### FederatedProbCover \(Alg\.[1](https://arxiv.org/html/2608.18634#alg1)\)\.

The key challenge in federating ProbCover is that its greedy criterion depends on the*global*number of samples newly covered by each query\. We replace direct access to the global embedding pool with a distributed proposal\-and\-count procedure\. At each round, each client performs a local ProbCover step and sends only the centroid of the region induced by its best candidate\. The server broadcasts these proposals, and clients return the number of currently uncovered local samples covered by each centroid\. Summing these counts yields the global coverage gain of every proposal without revealing the covered samples themselves\.

![Refer to caption](https://arxiv.org/arxiv/extracted/7968011/images/iid_coordination_gap_conf.png)\(a\)IID client partitions\.
![Refer to caption](https://arxiv.org/arxiv/extracted/7968011/images/noniid_coordination_gap_conf.png)\(b\)Non\-IID client partitions withα=0\.1\\alpha=0\.1\.

Figure 2:Empirical coordination gap across datasets and selection methods\. Error bars denote standard error over 3 random client splits\.The server selects the proposal with maximal global gain and queries the closest feasible sample to that centroid across clients, subject to client annotation budgets\. All clients then update their local coverage state using the selected centroid\. Thus, subsequent rounds account for coverage already obtained on*other clients*, explicitly reducing the cross\-client redundancy of independent selection\.

Algorithm 1FederatedProbCover1:whileannotation budget remainsdo

2:Each client

kkproposes centroid

ckc\_\{k\}of its locally best uncovered region\.

3:Server broadcasts

\{ck\}\\\{c\_\{k\}\\\}to all clients\.

4:Each client

jjreports local coverage gain

gj​kg\_\{jk\}for every

ckc\_\{k\}\.

5:Server selects

c∗=arg⁡max⁡∑jck⁡gj​kc^\{\*\}=\\arg\\max\_\{c\_\{k\}\}\\sum\_\{j\}g\_\{jk\}\.

6:Each client reports its closest feasible sample to

c∗c^\{\*\}and its distance\.

7:Server queries the globally closest candidate subject to client budgets\.

8:All clients mark samples covered by

c∗c^\{\*\}as covered\.

9:endwhile

##### FederatedTypiClust\.

TypiClust admits a particularly natural federated adaptation because its selection criterion is already defined through cluster\-level geometry\. We first construct global clusters using federatedkk\-means: clients communicate only per\-cluster sums and counts, from which the server updates the global centroids\. Given these centroids, each client reports, for every cluster, the distance to its closest eligible local sample\. The server orders clusters according to the TypiClust criterion \- prioritizing clusters containing fewer labeled samples and, as a tie\-breaker, larger clusters \- and queries the globally closest feasible sample to each selected centroid, while enforcing the per\-client annotation budgets\.

The two adaptations recover complementary forms of global geometric information from aggregates: FederatedProbCover estimates*global marginal coverage*through distributed counting, whereas FederatedTypiClust recovers*global cluster structure*through federated sufficient statistics\. Neither requires transmitting individual embeddings while retaining cross\-client coordination\.

## 5Empirical Results

Table 2:Full\-pipeline comparison between our method and the baseline adapted fromono2025exploring\. Our method performs globally coordinated selection in a shared federated embedding space and trains a shared classifier using FedAvg\. The baseline performs selection and classifier training independently at each client and uses the prediction of the most confident client classifier at inference\. Each pair uses the same active selection method\. Entries report mean test accuracy \(%\)±\\pmstandard error over three seeds at total annotation budgets corresponding to 1, 5, and 10 labeled samples per class\. Bold indicates the best outcome within each pair\.### 5\.1Evaluation Score

The coordination gapΔK\\Delta\_\{K\}in \([1](https://arxiv.org/html/2608.18634#S3.E1)\) measures the accuracy difference at a given annotation budget\. We summarize this gap across budgets using its normalized AUC counterpart, termed*Empirical Coordination Gap*and defined as follows:

###### Definition 2\(Empirical Coordination Gap\)\.

LetAUCcent\\mathrm\{AUC\}\_\{\\mathrm\{cent\}\}andAUCpc\\mathrm\{AUC\}\_\{\\mathrm\{pc\}\}denote the empirical areas under the centralized and per\-client accuracy–budget curves, computed by trapezoidal integration over the evaluated budgets\. We define the empirical coordination gap as

Δ^AUC=100⋅AUCcent−AUCpcAUCcent\.\\widehat\{\\Delta\}\_\{\\mathrm\{AUC\}\}=100\\cdot\\frac\{\\mathrm\{AUC\}\_\{\\mathrm\{cent\}\}\-\\mathrm\{AUC\}\_\{\\mathrm\{pc\}\}\}\{\\mathrm\{AUC\}\_\{\\mathrm\{cent\}\}\}\.

### 5\.2Results: Full Pipeline

We first evaluate the complete pipeline without embedding obfuscation, comparing our coordinated approach with the strengthened per\-client baseline described in Appendix[A](https://arxiv.org/html/2608.18634#A1)\. Both use the same shallow probabilistic classifier architecture; the effects of embedding obfuscation are evaluated separately in Section[5\.3](https://arxiv.org/html/2608.18634#S5.SS3)\.

##### IID Client Distributions

The results for IID clients are shown in Figure[2\(a\)](https://arxiv.org/html/2608.18634#S4.F2.sf1)and Table[2](https://arxiv.org/html/2608.18634#S5.T2)\. In Figure[3](https://arxiv.org/html/2608.18634#S5.F3)we further compare our method against high budget FAL\-specific approaches proposed in\[cao2023knowledge,kim2023re\]\. Across datasets and selection methods, our centralized pipeline consistently improves over the per\-client baseline, demonstrating a positive gap under IID partitions; this agrees with the redundancy\-based prediction of Section[3](https://arxiv.org/html/2608.18634#S3)\.

![Refer to caption](https://arxiv.org/arxiv/extracted/7968011/images/high_budget_baseline.png)Figure 3:Comparison against two representative high\-budget FAL methods\[cao2023knowledge,kim2023re\]\. The dashed line marks the accuracy achieved by our method using ProbCover selection with a substantially smaller annotation budget, highlighting the effectiveness of coordinated low\-budget selection even relative to methods evaluated with larger budgets\.Implementation details and methodology are provided in Appendix[A](https://arxiv.org/html/2608.18634#A1)\.

![Refer to caption](https://arxiv.org/arxiv/extracted/7968011/images/auc_vs_eps.png)Figure 4:The normalized AUC as a function of the embedding noise level\. Dashed lines show the corresponding aligned embedding per\-client baselines for each method\.
##### Non\-IID Client Distributions

The results for non\-IID clients are shown in Figure[2\(b\)](https://arxiv.org/html/2608.18634#S4.F2.sf2)and Table[2](https://arxiv.org/html/2608.18634#S5.T2)\. Across datasets and selection methods, the coordination gap now decreases substantially relative to the IID setting and sometimes becomes negative\. This reduction is consistent with the predicted heterogeneity reversal analyzed in Section[3](https://arxiv.org/html/2608.18634#S3)\. The negative gaps in some configurations are also consistent with Observation[1](https://arxiv.org/html/2608.18634#Thmobservation1), as maximum\-confidence aggregation may further benefit from client specialization\.

### 5\.3Privacy\-Preserving Data Obfuscation

In this section, we evaluate the two obfuscation mechanisms introduced in Section[4\.1](https://arxiv.org/html/2608.18634#S4.SS1.SSSx2): controlled embedding perturbation and centroid\-based communication\.

![Refer to caption](https://arxiv.org/arxiv/extracted/7968011/images/federated_algorithms_iid_fed_vs_cent.png)\(a\)The*empirical coordination gap*between centralized selection and its federated counterpart\. Lower indicates closer agreement with centralized selection\.
![Refer to caption](https://arxiv.org/arxiv/extracted/7968011/images/federated_algorithms_iid_fed_vs_cemb.png)\(b\)The*empirical coordination gap*over independent per\-client selection in the shared embedding space\. Higher indicates stronger benefit from coordination\.

Figure 5:Centroid\-based federated variants of ProbCover and TypiClust under IID client partitions\.Left:remaining gap to fully centralized selection\.Right:improvement over independent per\-client selection in the shared embedding space\. Both quantities are computed analogously to the empirical coordination gap; error bars denote standard error over three seeds\.Table 3:Test accuracy \(%\) at 1, 5, and 10 labeled samples per class, comparing fully centralized selection, the federated centroid\-based variant \(FedProbCover/FedTypiClust\), and the noiseless aligned\-embedding per\-client baseline \(CentEmb per\-client\), under IID client partitions\. Mean±\\pmstandard error over 3 seeds\. Bold marks the best of the three rows per column, within each method block\.##### Controlled embedding perturbation\.

We compare noisy centralized selection with independent per\-client selection in the aligned embedding space\. The noise levelϵ\\epsilondenotes the target expectedℓ2\\ell\_\{2\}displacement between each original and perturbed unit\-normalized embedding\. TypiClust and MaxHerding incur little or no accuracy loss up toϵ=0\.6\\epsilon=0\.6, whereas ProbCover is more sensitive to perturbation, see Figure[4](https://arxiv.org/html/2608.18634#S5.F4)and Appendix[D](https://arxiv.org/html/2608.18634#A4)for details\.

##### Federated Versions of the “Classic” AL Selection Algorithms\.

We also evaluate the two aggregate\-based FAL methods described in Section[4\.2](https://arxiv.org/html/2608.18634#S4.SS2)under IID client partitions\. Figure[5](https://arxiv.org/html/2608.18634#S5.F5)and Table[3](https://arxiv.org/html/2608.18634#S5.T3)report their remaining gap to centralized selection and their improvement over independent per\-client selection in the shared embedding space\. Both outperform independent per\-client selection, indicating that aggregate\-based cross\-client coordination reduces query redundancy\. FederatedTypiClust closely matches centralized selection, whereas FederatedProbCover retains a larger gap\.

![Refer to caption](https://arxiv.org/arxiv/extracted/7968011/images/iid_cent_vs_perclient.png)\(a\)IID client partitions\.
![Refer to caption](https://arxiv.org/arxiv/extracted/7968011/images/noniid_cent_vs_perclient.png)\(b\)Non\-IID client partitions\.

Figure 6:Same\-embedding selection\-stage ablation\. In both settings, centralized and per\-client selection operate on the same federated embedding, isolating the effect of global query coordination from representation quality\.Left:Empirical coordination gap under IID client partitions across datasets and selection methods\.Right:Empirical coordination gap under non\-IID client partitions as the Dirichlet parameterα\\alphavaries\. Positive values indicate that centralized selection improves over independent per\-client selection, while negative values indicate that per\-client selection performs better\.

### 5\.4Ablation Study

To isolate query coordination from representation quality, we compare centralized and per\-client selection within the same federated embedding\. Figure[6](https://arxiv.org/html/2608.18634#S5.F6)shows a positive coordination benefit under IID partitions that decreases and can become negative with increasing heterogeneity, mirroring the full\-pipeline trend\. This supports the interpretation that the reversal arises from the selection stage itself\. Absolute accuracies are reported in Appendix[C](https://arxiv.org/html/2608.18634#A3)\.

## 6Discussion

Our results highlight the importance of globally coordinated query selection in low\-budget FAL\. By using a shared federated representation, our framework enables selection across clients while keeping raw data private and downstream training federated\. This allows standard low\-budget AL methods to reduce cross\-client redundancy without violating privacy constraints\. Our results also show that coordination utility depends strongly on client heterogeneity: its benefit is largest under homogeneous partitions and declines as heterogeneity itself provides cross\-client diversity\.

These results suggest that low\-budget FAL is fundamentally a joint selection–representation problem\. Coordination is most beneficial when clients are similar enough to produce redundant local queries and can be compared meaningfully in a shared representation space\. More broadly, our framework provides a modular foundation for future FAL methods that jointly adapt selection, representation learning, and privacy\-preserving coordination\.

### Acknowledgments

This work was supported by a grant from the Gatsby Charitable Foundation and AFOSR award FA8655\-24\-1\-7006\.

## References

## Appendix

## Appendix AExperimental Setup and Methodology

Abl We evaluate CIFAR\-10, CIFAR\-100\[krizhevsky2009learning\], and ImageNet\-100\[deng2009imagenet\]using TypiClust, MaxHerding, and ProbCover \(see Section[2](https://arxiv.org/html/2608.18634#S2)\)\. Following the procedure described in Section[4](https://arxiv.org/html/2608.18634#S4), the SimCLR feature extractor is trained with FedAvg for 1,000 rounds, with one local epoch per round and batch size 256\. Downstream classification uses a one\-hidden\-layer network with 256 hidden units trained with FedAvg\.

We compare against a strengthened per\-client baseline adapted fromono2025exploring, which was shown to outperform other FAL baselines in the low\-budget regime\. In this baseline, clients learn separate feature spaces and perform active selection locally\. Since these feature spaces are not aligned, standard FL aggregation is not directly applicable; we therefore train one downstream pipeline per client\. At inference time, all client pipelines evaluate each test sample, and the final prediction is taken from the pipeline assigning the highest probability to its predicted class\. We use this maximum\-confidence aggregation under both IID and non\-IID client partitions\. This further strengthens the original ResNet\-based protocol of Ono et al\.\[ono2025exploring\], as classifiers trained on self\-supervised features have been shown to substantially outperform ResNet\-based classifiers trained on raw images in the low\-budget regime\[hacohen2022active,yehuda2022active\]\.

In all experiments throughout the paper, CIFAR\-10 is split across two clients, while CIFAR\-100 and ImageNet\-100 are split across four clients\. Client partitions are generated as described in Appendix[E](https://arxiv.org/html/2608.18634#A5)\. Selection hyperparameters are set according to the values specified in Appendix[G](https://arxiv.org/html/2608.18634#A7)\. All experiments are repeated over three random seeds \(0\-2\), and we report the mean performance together with the standard error across seeds\.

The experiments were run on a small local GPU cluster; each experiment used between 1 and 4 GPUs, with runtimes ranging from roughly one hour to one day depending on the dataset, method, and budget configuration\.

## Appendix BClient\-Constrained Active Selection

We adapt ProbCover and TypiClust to global selection under client\-level annotation budgets\.

##### Client\-constrained ProbCover\.

Let𝒳\\mathcal\{X\}denote the embedding space and let

X=⨆i=1KXi⊆𝒳X=\\bigsqcup\_\{i=1\}^\{K\}X\_\{i\}\\subseteq\\mathcal\{X\}denote the global unlabeled set, whereXiX\_\{i\}is held by clientii\. LetPPdenote the underlying data distribution,bbthe global annotation budget, andbib\_\{i\}the annotation budget of clientii, assuming∑i=1Kbi=b\\sum\_\{i=1\}^\{K\}b\_\{i\}=b\.

Following ProbCover\[yehuda2022active\], define

Bδ​\(x\)\\displaystyle B\_\{\\delta\}\(x\)=\{x′∈𝒳:‖x−x′‖2≤δ\},\\displaystyle=\\left\\\{x^\{\\prime\}\\in\\mathcal\{X\}:\\\|x\-x^\{\\prime\}\\\|\_\{2\}\\leq\\delta\\right\\\},C⁡\(L,δ\)\\displaystyle C\(L,\\delta\)=⋃x∈LBδ​\(x\)\.\\displaystyle=\\bigcup\_\{x\\in L\}B\_\{\\delta\}\(x\)\.
###### Definition 3\(Client\-Constrained Max Probability Cover\)\.

The client\-constrained extension of Max Probability Cover is

L⋆∈arg⁡maxL⊆X,\|L\|=b\|L∩Xi\|≤bi,∀i⁡P⁡\(C⁡\(L,δ\)\)\.L^\{\\star\}\\in\\arg\\max\_\{\\begin\{subarray\}\{c\}L\\subseteq X,\\ \|L\|=b\\\\ \|L\\cap X\_\{i\}\|\\leq b\_\{i\},\\ \\forall i\\end\{subarray\}\}P\\bigl\(C\(L,\\delta\)\\bigr\)\.

Using the empirical distribution onXX, this becomes

L⋆∈arg⁡maxL⊆X,\|L\|=b\|L∩Xi\|≤bi,∀i​\|⋃x∈L\(Bδ​\(x\)∩X\)\|\.L^\{\\star\}\\in\\arg\\max\_\{\\begin\{subarray\}\{c\}L\\subseteq X,\\ \|L\|=b\\\\ \|L\\cap X\_\{i\}\|\\leq b\_\{i\},\\ \\forall i\\end\{subarray\}\}\\left\|\\bigcup\_\{x\\in L\}\\left\(B\_\{\\delta\}\(x\)\\cap X\\right\)\\right\|\.This is a typed, or colored, maximum\-coverage problem, where each candidate is associated with its originating client\.

The coverage objective remains monotone submodular\. The feasible sets

ℐ=\{L⊆X:\|L\|≤b,\|L∩Xi\|≤bi∀i\}\\mathcal\{I\}=\\left\\\{L\\subseteq X:\|L\|\\leq b,\\ \|L\\cap X\_\{i\}\|\\leq b\_\{i\}\\ \\forall i\\right\\\}form a truncated partition matroid\. Consequently, the standard greedy algorithm achieves a1/21/2approximation, compared with the\(1−1/e\)\(1\-1/e\)guarantee obtained by ProbCover under a single cardinality constraint\.

At each iteration, the server selects the feasible candidate with the largest marginal coverage gain,

Δ⁡\(x∣L\)=\|\(Bδ​\(x\)∩X\)∖⋃z∈L\(Bδ​\(z\)∩X\)\|\.\\Delta\(x\\mid L\)=\\left\|\\left\(B\_\{\\delta\}\(x\)\\cap X\\right\)\\setminus\\bigcup\_\{z\\in L\}\\left\(B\_\{\\delta\}\(z\)\\cap X\\right\)\\right\|\.Candidates belonging to clients whose budgets have been exhausted are excluded, and selection continues until the global budgetbbis reached\.

##### Client\-constrained TypiClust\.

TypiClust is applied to the aggregated embedding set, with cluster representatives selected subject to the client\-level annotation budgets\.

## Appendix CAblation Study

Tables[4](https://arxiv.org/html/2608.18634#A3.T4)and[5](https://arxiv.org/html/2608.18634#A3.T5)provide the absolute accuracies underlying the same\-embedding coordination\-gap results in Figure[6](https://arxiv.org/html/2608.18634#S5.F6), for IID and non\-IID data client distributions respectively\. Centralized and per\-client selection use the identical Phase\-I embedding and downstream training protocol, differing only in query selection\. Note that Table[5](https://arxiv.org/html/2608.18634#A3.T5)reports absolute accuracies as the Dirichlet parameter varies\. The decreasing coordination benefit asα\\alphadecreases corresponds to the trend summarized in Figure[6](https://arxiv.org/html/2608.18634#S5.F6)\.

Table 4:Same\-embedding selection\-stage ablation \(Figure[6\(a\)](https://arxiv.org/html/2608.18634#S5.F6.sf1), IID\): test accuracy \(%\) at 1, 5, and 10 labeled samples per class, comparing centralized selection to per\-client selection on the identical shared embedding \(CentEmb per\-client\)\. Mean±\\pmstandard error over 3 seeds\. Bold marks the better of the pair per column, within each method block\.Table 5:Same\-embedding selection\-stage ablation \(Figure[6\(b\)](https://arxiv.org/html/2608.18634#S5.F6.sf2), non\-IID, CIFAR\-100\): test accuracy \(%\) at 1, 5, and 10 labeled samples per class, comparing centralized selection to per\-client selection on the identical shared embedding \(CentEmb per\-client\), across Dirichlet heterogeneityα∈\{0\.1,1,10\}\\alpha\\in\\\{0\.1,1,10\\\}\. Mean±\\pmstandard error over 3 seeds\. Bold marks the better of the pair per column, within each method block\.Table 6:Test accuracy \(%\) at 1, 5, and 10 labeled samples per class on CIFAR\-100, for centralized active selection under increasing embedding noiseε\\varepsilon\(rows\), for each method \(column groups\)\. Mean±\\pmstandard error over 3 seeds\. The bottom row is the noiseless aligned\-embedding per\-client baseline \(CentEmb per\-client\)\.
## Appendix DEmbedding Perturbation

Let𝐗∈ℝN×d\\mathbf\{X\}\\in\\mathbb\{R\}^\{N\\times d\}denote the matrix of embeddings, where each row𝐱i\\mathbf\{x\}\_\{i\}is normalized such that‖𝐱i‖2=1\\\|\\mathbf\{x\}\_\{i\}\\\|\_\{2\}=1\. We apply a stochastic perturbation that preserves unit norm while controlling the expectedℓ2\\ell\_\{2\}displacement\.

For each embedding𝐱i\\mathbf\{x\}\_\{i\}, we sample a Gaussian vector

𝐠∼𝒩⁡\(𝟎,Id\),\\mathbf\{g\}\\sim\\mathcal\{N\}\(\\mathbf\{0\},I\_\{d\}\),and project it onto the tangent space of the unit sphere at𝐱i\\mathbf\{x\}\_\{i\}:

𝐠⟂=𝐠−\(𝐠⊤​𝐱i\)​𝐱i,\\mathbf\{g\}\_\{\\perp\}=\\mathbf\{g\}\-\(\\mathbf\{g\}^\{\\top\}\\mathbf\{x\}\_\{i\}\)\\mathbf\{x\}\_\{i\},which ensures𝐠⟂⊤​𝐱i=0\\mathbf\{g\}\_\{\\perp\}^\{\\top\}\\mathbf\{x\}\_\{i\}=0\. We then scale the perturbation as

𝝃i=σd−1​𝐠⟂,\\boldsymbol\{\\xi\}\_\{i\}=\\frac\{\\sigma\}\{\\sqrt\{d\-1\}\}\\mathbf\{g\}\_\{\\perp\},so that

𝔼​‖𝝃i‖22=σ2\.\\mathbb\{E\}\\\|\\boldsymbol\{\\xi\}\_\{i\}\\\|\_\{2\}^\{2\}=\\sigma^\{2\}\.
The perturbed embedding is defined by

𝐱i′=𝐱i\+𝝃i‖𝐱i\+𝝃i‖2,\\mathbf\{x\}\_\{i\}^\{\\prime\}=\\frac\{\\mathbf\{x\}\_\{i\}\+\\boldsymbol\{\\xi\}\_\{i\}\}\{\\\|\\mathbf\{x\}\_\{i\}\+\\boldsymbol\{\\xi\}\_\{i\}\\\|\_\{2\}\},which guarantees‖𝐱i′‖2=1\\\|\\mathbf\{x\}\_\{i\}^\{\\prime\}\\\|\_\{2\}=1\.

##### Choice ofσ\\sigma\.

The parameterσ\\sigmais chosen such that the expected displacement after normalization matches a target valueϵ\\epsilon\. Since𝝃i⟂𝐱i\\boldsymbol\{\\xi\}\_\{i\}\\perp\\mathbf\{x\}\_\{i\}, we have

‖𝐱i\+𝝃i‖2=1\+‖𝝃i‖22\.\\\|\\mathbf\{x\}\_\{i\}\+\\boldsymbol\{\\xi\}\_\{i\}\\\|\_\{2\}=\\sqrt\{1\+\\\|\\boldsymbol\{\\xi\}\_\{i\}\\\|\_\{2\}^\{2\}\}\.
In high dimensions,‖𝝃i‖22\\\|\\boldsymbol\{\\xi\}\_\{i\}\\\|\_\{2\}^\{2\}concentrates sharply around its expectationσ2\\sigma^\{2\}, yielding the approximation

𝐱i⊤​𝐱i′≈11\+σ2\.\\mathbf\{x\}\_\{i\}^\{\\top\}\\mathbf\{x\}\_\{i\}^\{\\prime\}\\approx\\frac\{1\}\{\\sqrt\{1\+\\sigma^\{2\}\}\}\.
The squared displacement is therefore

‖𝐱i′−𝐱i‖22=2−2​𝐱i⊤​𝐱i′≈2−21\+σ2\.\\\|\\mathbf\{x\}\_\{i\}^\{\\prime\}\-\\mathbf\{x\}\_\{i\}\\\|\_\{2\}^\{2\}=2\-2\\,\\mathbf\{x\}\_\{i\}^\{\\top\}\\mathbf\{x\}\_\{i\}^\{\\prime\}\\approx 2\-\\frac\{2\}\{\\sqrt\{1\+\\sigma^\{2\}\}\}\.
Matching the expected displacement toϵ2\\epsilon^\{2\}gives

ϵ≈2−21\+σ2,\\epsilon\\approx\\sqrt\{2\-\\frac\{2\}\{\\sqrt\{1\+\\sigma^\{2\}\}\}\},which yields

σ=1\(1−ϵ2/2\)2−1\.\\sigma=\\sqrt\{\\frac\{1\}\{\(1\-\\epsilon^\{2\}/2\)^\{2\}\}\-1\}\.
Forϵ<2\\epsilon<\\sqrt\{2\}, this mapping is bijective inσ\\sigma, ensuring stable calibration\.

##### Properties\.

This construction has three key properties: \(i\) it preserves unit norm exactly, \(ii\) it induces an isotropic perturbation in the tangent space, and \(iii\) it provides explicit control over the expected displacement viaϵ\\epsilon, with strong concentration in high dimension\.

### Empirical Evaluation

We evaluate embedding obfuscation by adding noise before clients transmit embeddings to the server\. Our goal is to determine how much perturbation can be introduced while preserving the gains of centralized selection\. We compare noisy centralized selection against independent per\-client selection in the aligned embedding space, following the protocol in Appendix[C](https://arxiv.org/html/2608.18634#A3)\. Results are shown in Table[6](https://arxiv.org/html/2608.18634#A3.T6), which reports the absolute accuracies underlying Figure[4](https://arxiv.org/html/2608.18634#S5.F4)\.

## Appendix EClient Split Generation Methodology

We consider both IID and non\-IID client partitions\. In the IID setting, we randomly split the balanced dataset across clients, so that each client receives approximately the same number of samples and the label distribution is preserved across clients\.

In the non\-IID setting, each client is assigned data with a distinct label distribution, generated using a Dirichlet\-based partitioning scheme\. LetCCdenote the number of classes andKKthe number of clients\. For each clientk∈\{1,…,K\}k\\in\\\{1,\\dots,K\\\}, we sample a class\-probability vector

pk∼Dir⁡\(α​𝟏\),p\_\{k\}\\sim\\mathrm\{Dir\}\(\\alpha\\mathbf\{1\}\),where𝟏∈ℝC\\mathbf\{1\}\\in\\mathbb\{R\}^\{C\}is the all\-ones vector andα\>0\\alpha\>0is a concentration parameter\.

Given these sampled distributions, the dataset is partitioned class\-wise\. For each classcc, we collect all samples belonging to that class and distribute them among clients according to the probabilities\{pk​\[c\]\}k=1K\\\{p\_\{k\}\[c\]\\\}\_\{k=1\}^\{K\}\. This assignment is performed while enforcing that each client receives approximately the same total number of samples, thereby preserving balanced dataset sizes across clients while inducing heterogeneous label distributions\.

The parameterα\\alphacontrols the degree of heterogeneity: forα≪1\\alpha\\ll 1, the resulting distributions are highly skewed, leading to strongly non\-IID client data; forα≈1\\alpha\\approx 1, the distributions are moderately heterogeneous; and forα≫1\\alpha\\gg 1, the class proportions concentrate around uniformity, yielding approximately IID client distributions\.

## Appendix FDerivation of the Redundancy Gap

This appendix derives Proposition[1](https://arxiv.org/html/2608.18634#Thmproposition1)and Corollaries[2](https://arxiv.org/html/2608.18634#Thmcorollary2)and[1](https://arxiv.org/html/2608.18634#Thmcorollary1), and relates the redundancy gap to the coordination gap\.

### F\.1Expected Coverage

Let

Sloc=⋃k=1KSk⋆,LK=∑k=1K𝔼⁡\[Φ⁡\(Sk⋆\)\]\.S\_\{\\mathrm\{loc\}\}=\\bigcup\_\{k=1\}^\{K\}S\_\{k\}^\{\\star\},\\qquad L\_\{K\}=\\sum\_\{k=1\}^\{K\}\\mathbb\{E\}\[\\Phi\(S\_\{k\}^\{\\star\}\)\]\.For each cellCmC\_\{m\}, define

Im=𝟏\{Sloc∩Cm≠∅\}\.I\_\{m\}=\\mathbf\{1\}\\\{S\_\{\\mathrm\{loc\}\}\\cap C\_\{m\}\\neq\\emptyset\\\}\.Then

Φ⁡\(Sloc\)=∑m=1MIm\.\\Phi\(S\_\{\\mathrm\{loc\}\}\)=\\sum\_\{m=1\}^\{M\}I\_\{m\}\.By linearity of expectation,

𝔼⁡\[Φ⁡\(Sloc\)\]=∑m=1MPr⁡\(Sloc∩Cm≠∅\)\.\\mathbb\{E\}\[\\Phi\(S\_\{\\mathrm\{loc\}\}\)\]=\\sum\_\{m=1\}^\{M\}\\Pr\(S\_\{\\mathrm\{loc\}\}\\cap C\_\{m\}\\neq\\emptyset\)\.\(11\)
A cell is not covered bySlocS\_\{\\mathrm\{loc\}\}if none of the clients covers it\. Conditional independence gives

Pr⁡\(Sloc∩Cm=∅\)\\displaystyle\\Pr\(S\_\{\\mathrm\{loc\}\}\\cap C\_\{m\}=\\emptyset\)=∏k=1KPr⁡\(Sk⋆∩Cm=∅\)\\displaystyle=\\prod\_\{k=1\}^\{K\}\\Pr\(S\_\{k\}^\{\\star\}\\cap C\_\{m\}=\\emptyset\)=∏k=1K\(1−ak,m\)\.\\displaystyle=\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)\.Therefore,

𝔼⁡\[Φ⁡\(Sloc\)\]=∑m=1M\(1−∏k=1K\(1−ak,m\)\)\.\\mathbb\{E\}\[\\Phi\(S\_\{\\mathrm\{loc\}\}\)\]=\\sum\_\{m=1\}^\{M\}\\left\(1\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)\\right\)\.\(12\)

### F\.2Local Coverage and Redundancy

For each client,

Φ\(Sk⋆\)=∑m=1M𝟏\{Sk⋆∩Cm≠∅\}\.\\Phi\(S\_\{k\}^\{\\star\}\)=\\sum\_\{m=1\}^\{M\}\\mathbf\{1\}\\\{S\_\{k\}^\{\\star\}\\cap C\_\{m\}\\neq\\emptyset\\\}\.Hence,

𝔼⁡\[Φ⁡\(Sk⋆\)\]\\displaystyle\\mathbb\{E\}\[\\Phi\(S\_\{k\}^\{\\star\}\)\]=∑m=1M𝔼\[𝟏\{Sk⋆∩Cm≠∅\}\]\\displaystyle=\\sum\_\{m=1\}^\{M\}\\mathbb\{E\}\\left\[\\mathbf\{1\}\\\{S\_\{k\}^\{\\star\}\\cap C\_\{m\}\\neq\\emptyset\\\}\\right\]=∑m=1MPr⁡\(Sk⋆∩Cm≠∅\)\\displaystyle=\\sum\_\{m=1\}^\{M\}\\Pr\(S\_\{k\}^\{\\star\}\\cap C\_\{m\}\\neq\\emptyset\)=∑m=1Mak,m\.\\displaystyle=\\sum\_\{m=1\}^\{M\}a\_\{k,m\}\.Consequently,

LK=∑k=1K∑m=1Mak,m\.L\_\{K\}=\\sum\_\{k=1\}^\{K\}\\sum\_\{m=1\}^\{M\}a\_\{k,m\}\.\(13\)
The quantityLKL\_\{K\}counts coverage with multiplicity: a cell covered by multiple clients contributes once for each client\. Define the expected cross\-client redundancy as

Δ¯Kred=LK−𝔼⁡\[Φ⁡\(Sloc\)\]\.\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=L\_\{K\}\-\\mathbb\{E\}\[\\Phi\(S\_\{\\mathrm\{loc\}\}\)\]\.\(14\)Using Eqs\. \([12](https://arxiv.org/html/2608.18634#A6.E12)\) and \([13](https://arxiv.org/html/2608.18634#A6.E13)\),

Δ¯Kred=∑m=1M\[∑k=1Kak,m−\(1−∏k=1K\(1−ak,m\)\)\]\.\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=\\sum\_\{m=1\}^\{M\}\\left\[\\sum\_\{k=1\}^\{K\}a\_\{k,m\}\-\\left\(1\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)\\right\)\\right\]\.\(15\)
The expected coordination gap admits the exact decomposition

Δ¯K=\(𝔼⁡\[ΦB⋆\]−LK\)\+Δ¯Kred\.\\bar\{\\Delta\}\_\{K\}=\\left\(\\mathbb\{E\}\[\\Phi\_\{B\}^\{\\star\}\]\-L\_\{K\}\\right\)\+\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}\.\(16\)The first term measures the loss due to ineffective local coverage, whileΔ¯Kred\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}measures redundancy across clients\.

In the low\-budget regime, a locally effective diversity\-based selector is expected to cover approximately one new local cell with each query\. If clientkkhas budgetbkb\_\{k\}, then

𝔼⁡\[Φ⁡\(Sk⋆\)\]≈bk\.\\mathbb\{E\}\[\\Phi\(S\_\{k\}^\{\\star\}\)\]\\approx b\_\{k\}\.Since

B=∑k=1Kbk,B=\\sum\_\{k=1\}^\{K\}b\_\{k\},this gives

If the centralized selector also covers approximately one new cell per query, then

𝔼⁡\[ΦB⋆\]≈B,\\mathbb\{E\}\[\\Phi\_\{B\}^\{\\star\}\]\\approx B,and therefore

LK≈𝔼⁡\[ΦB⋆\]\.L\_\{K\}\\approx\\mathbb\{E\}\[\\Phi\_\{B\}^\{\\star\}\]\.
Under the idealized equality

LK=𝔼⁡\[ΦB⋆\],L\_\{K\}=\\mathbb\{E\}\[\\Phi\_\{B\}^\{\\star\}\],Eq\. \([16](https://arxiv.org/html/2608.18634#A6.E16)\) becomes

Δ¯K=Δ¯Kred=∑m=1M\[∑k=1Kak,m−\(1−∏k=1K\(1−ak,m\)\)\]\.\\bar\{\\Delta\}\_\{K\}=\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=\\sum\_\{m=1\}^\{M\}\\left\[\\sum\_\{k=1\}^\{K\}a\_\{k,m\}\-\\left\(1\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)\\right\)\\right\]\.\(17\)

### F\.3Disjoint Accessible Cells

We first show that pairwise\-disjoint accessible cell sets yield zero redundancy\.

###### Proof of Proposition[1](https://arxiv.org/html/2608.18634#Thmproposition1), Part 1\.

Assume

Ai∩Aj=∅∀i≠j\.A\_\{i\}\\cap A\_\{j\}=\\emptyset\\qquad\\forall i\\neq j\.For every cellCmC\_\{m\}, at most one client hasak,m\>0a\_\{k,m\}\>0\.

If allak,ma\_\{k,m\}are zero, then

1−∏k=1K\(1−ak,m\)=0=∑k=1Kak,m\.1\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)=0=\\sum\_\{k=1\}^\{K\}a\_\{k,m\}\.
Otherwise, letjjbe the unique client satisfyingaj,m\>0a\_\{j,m\}\>0\. Then

ak,m=0∀k≠j,a\_\{k,m\}=0\\qquad\\forall k\\neq j,and

1−∏k=1K\(1−ak,m\)\\displaystyle 1\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)=1−\(1−aj,m\)​∏k≠j\(1−ak,m\)\\displaystyle=1\-\(1\-a\_\{j,m\}\)\\prod\_\{k\\neq j\}\(1\-a\_\{k,m\}\)=1−\(1−aj,m\)\\displaystyle=1\-\(1\-a\_\{j,m\}\)=aj,m\\displaystyle=a\_\{j,m\}=∑k=1Kak,m\.\\displaystyle=\\sum\_\{k=1\}^\{K\}a\_\{k,m\}\.Thus, every cell contributes zero to Eq\. \([15](https://arxiv.org/html/2608.18634#A6.E15)\), implying

Δ¯Kred=0\.\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=0\.∎

### F\.4Shared Selection Mass

We next show that increasing a client’s selection probability for a cell can only increase that cell’s redundancy contribution\.

For a fixed cellCmC\_\{m\}, define

Δm=∑k=1Kak,m−\(1−∏k=1K\(1−ak,m\)\)\.\\Delta\_\{m\}=\\sum\_\{k=1\}^\{K\}a\_\{k,m\}\-\\left\(1\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)\\right\)\.
###### Proof of Proposition[1](https://arxiv.org/html/2608.18634#Thmproposition1), Part 2\.

Differentiating with respect toaj,ma\_\{j,m\}gives

∂Δm∂aj,m\\displaystyle\\frac\{\\partial\\Delta\_\{m\}\}\{\\partial a\_\{j,m\}\}=1−∂∂aj,m​\(1−∏k=1K\(1−ak,m\)\)\\displaystyle=1\-\\frac\{\\partial\}\{\\partial a\_\{j,m\}\}\\left\(1\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)\\right\)=1−∏k≠j\(1−ak,m\)\.\\displaystyle=1\-\\prod\_\{k\\neq j\}\(1\-a\_\{k,m\}\)\.Sinceak,m∈\[0,1\]a\_\{k,m\}\\in\[0,1\],

0≤∏k≠j\(1−ak,m\)≤1,0\\leq\\prod\_\{k\\neq j\}\(1\-a\_\{k,m\}\)\\leq 1,and therefore

∂Δm∂aj,m≥0\.\\frac\{\\partial\\Delta\_\{m\}\}\{\\partial a\_\{j,m\}\}\\geq 0\.
Equality holds if and only if

ak,m=0∀k≠j\.a\_\{k,m\}=0\\qquad\\forall k\\neq j\.Thus, the derivative is strictly positive exactly when another client selects fromCmC\_\{m\}with positive probability\. ∎

### F\.5Marginal Effect of an Additional Client

Finally, we characterize the additional redundancy introduced by a new client\. Define

cm\(K\)=1−∏k=1K\(1−ak,m\),c\_\{m\}^\{\(K\)\}=1\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\),the probability that at least one of the firstKKclients selects fromCmC\_\{m\}\.

###### Proof of Proposition[1](https://arxiv.org/html/2608.18634#Thmproposition1), Part 3\.

From Eq\. \([15](https://arxiv.org/html/2608.18634#A6.E15)\),

Δ¯Kred=∑m=1M\[∑k=1Kak,m−\(1−∏k=1K\(1−ak,m\)\)\]\.\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=\\sum\_\{m=1\}^\{M\}\\left\[\\sum\_\{k=1\}^\{K\}a\_\{k,m\}\-\\left\(1\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)\\right\)\\right\]\.Therefore,

Δ¯K\+1red−Δ¯Kred\\displaystyle\\bar\{\\Delta\}\_\{K\+1\}^\{\\mathrm\{red\}\}\-\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=∑m=1M\[aK\+1,m\\displaystyle=\\sum\_\{m=1\}^\{M\}\\Bigl\[a\_\{K\+1,m\}\+∏k=1K\+1\(1−ak,m\)−∏k=1K\(1−ak,m\)\]\.\\displaystyle\+\\prod\_\{k=1\}^\{K\+1\}\(1\-a\_\{k,m\}\)\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)\\Bigr\]\.
For each cell,

∏k=1K\+1\(1−ak,m\)=\(1−aK\+1,m\)​∏k=1K\(1−ak,m\)\.\\prod\_\{k=1\}^\{K\+1\}\(1\-a\_\{k,m\}\)=\(1\-a\_\{K\+1,m\}\)\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)\.Hence,

\(1−∏k=1K\+1\(1−ak,m\)\)−\(1−∏k=1K\(1−ak,m\)\)\\displaystyle\\left\(1\-\\prod\_\{k=1\}^\{K\+1\}\(1\-a\_\{k,m\}\)\\right\)\-\\left\(1\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)\\right\)=aK\+1,m​∏k=1K\(1−ak,m\)\.\\displaystyle=a\_\{K\+1,m\}\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)\.Substituting this identity yields

Δ¯K\+1red−Δ¯Kred\\displaystyle\\bar\{\\Delta\}\_\{K\+1\}^\{\\mathrm\{red\}\}\-\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=∑m=1MaK\+1,m​\[1−∏k=1K\(1−ak,m\)\]\\displaystyle=\\sum\_\{m=1\}^\{M\}a\_\{K\+1,m\}\\left\[1\-\\prod\_\{k=1\}^\{K\}\(1\-a\_\{k,m\}\)\\right\]=∑m=1MaK\+1,m​cm\(K\)\.\\displaystyle=\\sum\_\{m=1\}^\{M\}a\_\{K\+1,m\}c\_\{m\}^\{\(K\)\}\.∎

We next show that adding a client whose accessible cells are disjoint from those of the existing clients introduces no additional redundancy\.

###### Proof of Corollary[2](https://arxiv.org/html/2608.18634#Thmcorollary2)\.

If

AK\+1∩⋃k=1KAk=∅,A\_\{K\+1\}\\cap\\bigcup\_\{k=1\}^\{K\}A\_\{k\}=\\emptyset,then

aK\+1,m\>0⟹cm\(K\)=0\.a\_\{K\+1,m\}\>0\\quad\\Longrightarrow\\quad c\_\{m\}^\{\(K\)\}=0\.Therefore,

Δ¯K\+1red−Δ¯Kred=∑m=1MaK\+1,m​cm\(K\)=0\.\\bar\{\\Delta\}\_\{K\+1\}^\{\\mathrm\{red\}\}\-\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=\\sum\_\{m=1\}^\{M\}a\_\{K\+1,m\}c\_\{m\}^\{\(K\)\}=0\.∎

### F\.6IID Clients

We finally show that, under identical cell\-level selection probabilities, the redundancy gap is nondecreasing in the number of clients\.

###### Proof of Corollary[1](https://arxiv.org/html/2608.18634#Thmcorollary1)\.

Under the IID assumption,

for every clientkk\. Substituting into Eq\. \([15](https://arxiv.org/html/2608.18634#A6.E15)\) gives

Δ¯Kred=∑m=1M\[K​am−\(1−\(1−am\)K\)\]\.\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=\\sum\_\{m=1\}^\{M\}\\left\[Ka\_\{m\}\-\\left\(1\-\(1\-a\_\{m\}\)^\{K\}\\right\)\\right\]\.
For a fixed cell, define

fm​\(K\)=K​am−\(1−\(1−am\)K\)\.f\_\{m\}\(K\)=Ka\_\{m\}\-\\left\(1\-\(1\-a\_\{m\}\)^\{K\}\\right\)\.Its finite difference is

fm​\(K\+1\)−fm​\(K\)\\displaystyle f\_\{m\}\(K\+1\)\-f\_\{m\}\(K\)=am−am​\(1−am\)K\\displaystyle=a\_\{m\}\-a\_\{m\}\(1\-a\_\{m\}\)^\{K\}=am​\[1−\(1−am\)K\]\\displaystyle=a\_\{m\}\\left\[1\-\(1\-a\_\{m\}\)^\{K\}\\right\]≥0\.\\displaystyle\\geq 0\.Summing over cells gives

Δ¯K\+1red−Δ¯Kred=∑m=1Mam​\[1−\(1−am\)K\]≥0\.\\bar\{\\Delta\}\_\{K\+1\}^\{\\mathrm\{red\}\}\-\\bar\{\\Delta\}\_\{K\}^\{\\mathrm\{red\}\}=\\sum\_\{m=1\}^\{M\}a\_\{m\}\\left\[1\-\(1\-a\_\{m\}\)^\{K\}\\right\]\\geq 0\.Thus, under fixed per\-client selection behavior, the expected redundancy gap is nondecreasing in the number of IID clients\. ∎

## Appendix GHyperparameters

Table[7](https://arxiv.org/html/2608.18634#A7.T7)lists the selection hyperparameters used in our experiments\. ProbCover radii follow the dataset\-specific values recommended byyehuda2022active; MaxHerding uses the fixed Gaussian\-kernel lengthscaleσ=1\\sigma=1frombae2024maxherding\.

Table 7:Selection hyperparameters used in our experiments\.