acceptodds
Under review as a conference paper at ICLR 2027

Vertical Federated Learning as a Social Choice Problem

Abstract

Centralized data aggregation in modern machine learning increasingly conflicts with privacy laws, security risks, and settings where data pooling is impossible. Federated learning addresses this by bringing models to the data. Unlike horizontal federated learning (HFL), where agents share a feature space across distinct individuals, many real-world scenarios require the opposite: agents hold distinct feature sets for overlapping populations. This decentralized setting defines vertical federated learning (VFL). To enable a VFL central server to aggregate multi-agent predictions without accessing raw data or internal models, we propose a voting-theory-based framework satisfying strict privacy and minimal-invasiveness constraints. In this approach, agents submit round-wise predictions (or “votes”) based on their local features, which the server aggregates into a final decision. We prove that any stationary aggregation rule incurs linear regret, motivating a dynamic generalization where agent weights evolve as evidence accumulates. Consequently, we introduce Trust-Based Perpetual Voting (TBPV), adapting classical Perpetual Voting for accuracy-driven tasks by concentrating influence on agents the server trusts most. This is primarily a theoretical contribution: our experiments are a proof of concept, intended to check that the mechanism behaves as the theory predicts on controlled vertical partitions, rather than to establish state-of-the-art performance.

Primary area:
learning theory
Keywords:
federated learning, computational social choice, vertical federated learning, online learning, social choice, voting, aggregation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_oG7POpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies output-only aggregation in vertical federated learning: each party predicts from its own feature slice, and the server sees neither data, models, nor gradients, and never observes the true label. The authors cast this as a social choice problem. Using Young's (1975) characterisations, they argue that Borda is the best static rule, and they show that for every stationary rule there exists a data-generating distribution on which it incurs linear expected regret. They then propose Trust-Based Perpetual Voting (TBPV), which replaces the "down-weight the winners" satisfaction update of perpetual voting with a trust update that raises an agent's weight when it agrees with the consensus. The authors claim to establish mean-square convergence of the trust weights, that TBPV satisfies trustworthiness (fixed-point trust is strictly increasing in accuracy), that the perpetual-voting satisfaction guarantee carries an accuracy cost and on some instances cannot be met by eventually accuracy-ordered rules, and, under a concentration condition, that the trust fixed point attains higher collective accuracy than the approval fixed point. Validation consists of a proof-of-concept evaluation on two tabular datasets (Letter, Sensorless) with five parties, comparing TBPV (Kalman and EigenTrust variants) against the satisfaction class of perpetual voting rules and Hedge variants under contiguous and shuffled feature partitions.

Critical strengths

1. A clean and genuinely new accuracy–satisfaction trade-off (Thm 5.5, Cor 5.6). The two-agent instance gives an explicit bound on the accuracy cost of the perpetual-voting satisfaction guarantee, and Cor 5.6 shows that for every β_sat there is an instance on which no eventually accuracy-ordered rule can satisfy the guarantee with that parameter. The proof is correct and the result has no counterpart in the label-aggregation literature. Why it is consequential: it is the paper's most solid and original contribution, and it gives the social-choice framing of output-only VFL real content by showing that fairness and accuracy objectives cannot in general be reconciled.

2. An insightful decomposition of collective accuracy (Lemma B.8). Collective accuracy is separated into the alignment of pivotality with signal and total influence, and Remark B.9 shows why alignment alone cannot determine accuracy. Why it is consequential: it identifies, to leading order in the signal, what a weighting rule must achieve to improve accuracy, which is useful beyond this paper even though the dominance result built on it is not yet established.

Critical weaknesses

1. The agreement probability omits each agent's influence on the consensus, so trustworthiness (Prop 5.3) is not established. The mean-field analysis assumes the agreement probability q_v = ρp_v + (1−ρ)(1−p_v)/(K−1), i.e. that an agent's vote is independent of whether the consensus is correct. But each agent is itself a voter: the more weight it carries, the more it shapes the consensus and the more often it agrees with it. This self-reinforcement is the known failure mode of consensus-agreement weighting, and the current argument does not rule out a stable fixed point at which a heavily weighted but less accurate agent keeps high trust because it largely determines the consensus it agrees with (for example, one reached from an early lead). The key stability step of Lemma 5.2, on which Prop 5.3 depends, is also only sketched. Why it is consequential: trustworthiness is the premise of the entire method. The same agreement probability underlies Prop 5.3, Lemmas B.10 and B.11 (and hence the fixed-point comparison in Thm 5.7), and Lemma B.1.

2. The convergence and dominance guarantees are not shown to hold in the configuration the paper evaluates. Thm 4.1 requires L_h + 2L_ρ < 1/√n, but with the experimental Kalman parameters (Q = 0.01, R = 0.1) the steady-state gain is about 0.27, giving L_h ≈ 0.73 > 1/√5 ≈ 0.447. Thm 5.7 bounds the remainder by 2·3^n·max θ_v², i.e. 486·max θ_v² for n = 5, and the paper does not show that the leading-order gap exceeds it in the experimental regime; the concentration condition C(γ*) ≥ C(α*) is not checked there either, and Remark B.16 shows it fails increasingly often over K = 3–5. Cor B.17 then asserts a strict long-run advantage, but it assumes a strict gap that Thm 5.7 does not give, and since Thm 4.1 guarantees only convergence in mean square to a ball around γ*, it would further need that gap to exceed the variation in collective accuracy over that ball. Why it is consequential: the paper positions itself as primarily theoretical and presents its experiments as checks that the mechanism behaves as the theory predicts, but the theorems as stated do not cover the configuration evaluated. The Introduction's claim that the trust fixed point "provably beats the approval fixed point" also rests on Thm 5.7, which gives only an inequality up to a remainder that is not shown to be dominated.

Questions for authors
  1. Once agent v's own pivotality is included in q_v, does Prop 5.3 still hold, and under what conditions (e.g., a bound on individual influence)? If the highest initial trust is given to the least accurate agent, does TBPV recover empirically?
  2. Do the guarantees cover the experimental configuration? Specifically: can the bound in Lemma B.1 be tightened (the h-term depends only on agent v's own coordinate) so that Thm 4.1 applies to the Kalman setting used, and under what conditions on n and max θ_v does the leading term in Thm 5.7 exceed the remainder bound, with C(γ*) ≥ C(α*) holding at K = 26 and K = 11?
Reviewer_PyipOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper formulates output-only vertical federated learning as sequential voting. Agents predict from their local feature slices, the server aggregates their predictions without observing ground-truth labels, and agents subsequently train toward the collective outcome. The proposed Trust-Based Perpetual Voting (TBPV) mechanism rewards agreement with that outcome, using either scalar Kalman-filter updates or pairwise EigenTrust scores.

The theoretical analysis addresses stationary-rule regret, trust dynamics, the relationship between trust and true accuracy, and a trade-off between collective accuracy and voter satisfaction. A fixed-point comparison with satisfaction-based voting is derived under conditional independence, symmetric errors, and a total-influence condition, with a second-order remainder. Proof-of-concept experiments use two tabular datasets, five vertically partitioned agents, and contiguous versus shuffled feature partitions.

Critical strengths
  1. The paper isolates a useful label-free aggregation problem. Separating output-only access, heterogeneous feature information, and unavailable online labels makes the information constraints explicit. Remark A.1 appropriately acknowledges that history alone cannot overcome observational indistinguishability, avoiding a universal no-regret claim for TBPV.

  2. The two-agent accuracy–satisfaction trade-off is informative. Theorem 5.5 quantifies how choosing the less accurate agent on disagreements can purchase satisfaction at a cost in accuracy under the specified independent, symmetric-error model. This provides a concrete explanation of why representation-oriented voting objectives may conflict with predictive performance.

Critical weaknesses
  1. The agreement model underlying trustworthiness ignores the agent’s influence on the collective outcome. Appendix B uses [ q_v(\gamma)=\rho(\gamma)p_v+ (1-\rho(\gamma))\frac{1-p_v}{K-1}. ] Conditional independence between agents does not imply independence between an agent and a collective decision computed from those agents. This distinction changes the conclusions.

Consider two binary agents with conditionally independent errors and accuracies (p_1=0.9), (p_2=0.6). Whenever agent 2 has greater weight, weighted singleton approval follows agent 2 on every disagreement. Its agreement with the collective is therefore 1; agent 1’s agreement is [ 0.9(0.6)+0.1(0.4)=0.58. ] For the admissible update (h(\gamma,z)=(\gamma+z)/2), the actual expected-update map has a locally stable fixed point ((0.58,1)). The less accurate agent receives greater trust, despite both agents being better than chance and collective accuracy exceeding chance. The update satisfies (A1)–(A3).

This contradicts Proposition 5.3 for the actual protocol. It also undermines the accuracy-alignment argument supporting Theorem 5.7. Treating the displayed agreement equation as an additional mean-field assumption would define an approximation, but would not establish the claimed property of TBPV itself.

  1. The claimed smoothing does not justify the convergence analysis. Remark B.2 correctly observes that finite weighted voting has piecewise-constant accuracy with jumps at decision boundaries. It then claims that random tie-breaking and averaging make this accuracy Lipschitz. Random tie-breaking only specifies behavior at a tie; it does not remove differing one-sided limits.

For example, with the two agents above, collective accuracy is 0.9 when agent 1 has greater weight, 0.6 when agent 2 has greater weight, and 0.75 at equal weights under uniform tie-breaking. This remains discontinuous. Consequently, the Lipschitz constant used in Lemma B.1 is not established by the proposed smoothing. A local analysis away from boundaries may be possible, but Theorem 4.1 additionally requires iterates to remain in that neighborhood without proving that they do. Its noise-floor bound also does not imply eventual accuracy ordering or exact convergence to a fixed point.

Questions for authors
  1. Agreement-model clarification: How is the factorization of (q_v) justified when the collective outcome includes agent (v)’s own vote? How do Proposition 5.3 and the fixed-point comparison accommodate the two-agent counterexample above? Is the intended mechanism instead based on leave-one-out consensus?

  2. Convergence clarification: What randomization smooths decisions away from exact ties? Please specify the resulting aggregation rule, derive its Lipschitz bound, and explain how the stochastic iterates are kept within the neighborhood required by Theorem 4.1.

  3. Axiomatic clarification: Section 4.3 says TBPV is not anonymous, whereas Proposition D.1 says it is. Moreover, Proposition D.2’s label permutation preserves each agent’s agreement indicator, so its trust update remains unchanged; the example does not demonstrate failure of neutrality under consistent relabeling of the history. What precise sequential definitions support these claims?

Reviewer_Cz22OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The work frames Vertical Federated Learning as a vote-theoretical social problem. Each round, clients transmit predictions to the server which merge them together into a final prediction, this mechanism is interpreted by the authors as vote submission and decision. The server uses a Trust-Based Perpetual Voting mechanism as a preference system to choose the agents it trusts more.

Critical strengths

I appreciate the authors' effort in framing VFL using mathematical techniques stemming for social sciences, and furthermore, as far as my own experience is concerned, this is one of the first contributions that relates that theory to Vertical FL. As far as my experience is concerned, I believe that the theoretical results are promising, but the current state of the manuscript is not mature yet.

Critical weaknesses

I believe that the contribution of this work is not clearly motivated in the paper, and that the advantages of using this approach are not properly discussed

As far as the theoretical contribution is concerned, there is a very limited discussion about the impact of these results in VFL current research, especially when it comes to compare their model to state-of-the-art frameworks

Theorems 3.1 and 3.2 appear a bit abruptly in the section, and, from a mathematician's perspective, the first theorem seems more of a definition, as it is placed in the manuscript. Overall, it looks to me that some theorems are unrelated to the narrative of the paper, and it is not clear what they add to the final framework

At times notation makes the paper hard to follow, as some symbols have been used without a proper introduction or definition (eg, Hi\mathcal{H}_i or the simplex Δ(Y)\Delta(\mathcal{Y})...). Moreover equations are not numbered.

During the last few years using mathematical tools from social network science in FL has gained popularity, therefore, I believe that a proper section that compares this work to this literature (heterogeneous, hybrid or vertical) should be included, to better place the authors' contribution

Questions for authors

Main concerns are listed in the weaknesses.

Other questions.

  1. Could the authors please clarify in line 091-092: the functional defined depends on σS\sigma_S, which doesn't appear in the formula directly. Also ℓ\ell has not been defined, is it ℓt\ell^t?

  2. Are the assumptions A1-A3 standard in the social science literature? If so could the authors point some references?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.