Hospitals, banks and insurers that each hold records of different people often want one interpretable decision tree: a model made of readable if-then rules. Today they have two options. They can grow the tree greedily, one split at a time, which exchanges data summaries at every node and adds privacy noise at every node. Or they can search over whole trees with a genetic algorithm, which comes with no guarantees. This proposal starts from a recent observation in centralized tree learning: greedy split choices do most of their damage near the root, and deeper down they are close to optimal Near-Optimal Decision Trees in a SPLIT Second. In a federated setting that suggests a natural division of labour. The clients jointly choose the top few levels of the tree exactly. Each client then grows the lower levels greedily on its own data, and those lower levels never leave the client.
The resulting model has a shared, auditable top, meaning the rules everyone agrees on, and client-specific bottoms that absorb differences between sites. The main technical claim is that, for a small top depth and binned thresholds, the exact best top can be found from a single upload per client. Each client sends one vector of loss values, and a secure-sum protocol reveals only the total across clients, never any client's own vector. The server then solves a small dynamic program. Only the shared top is released, so any differential-privacy cost is paid on a few selections rather than on every node of a deep tree.
Core Claim
The setting is horizontal federated learning: clients share the same features but hold different people. The model is a personalized tree. A shared top $T$ of depth $d_l$ uses globally agreed thresholds, and below each of its leaves client $c$ attaches its own greedily grown subtree, down to total depth $d$. We choose $T$ to minimize
$$ \sum_{c=1}^{C} L_c\big(T,\ \mathrm{greedy}_c(T)\big) + \lambda\,|T|, $$
where $L_c$ is client $c$'s training loss when its data is routed through $T$ and then through its own greedy completion $\mathrm{greedy}_c(T)$, $|T|$ is the number of leaves in the shared top, and $\lambda$ is a sparsity penalty. This matches the objective used by SPLIT, which does exhaustive search to a lookahead depth and completes greedily below it. The difference is that the greedy completion is now computed separately on each client's private data.
The key observation is that this objective splits cleanly. The loss of a candidate top is a sum, over its leaf regions, of per-client completion losses. Each leaf region is a path of at most $d_l$ splits. So each client can compute, locally, the greedy-completion loss for every possible path of length $d_l$ over the $p$ features, $B$ threshold bins and branch directions. A secure sum of these vectors gives the server exactly what it needs to find the optimal top by dynamic programming.
Here is the size for $d_l=2$ on a dataset like Adult. Adult has 14 features. With 32 bins there are $2pB \approx 900$ possible first-level subproblems, where $p$ is the number of features and the factor 2 counts the two branch directions. Pairs of such subproblems give on the order of $10^5$–$10^6$ numbers, a few megabytes uploaded once. SPLIT's result that the best lookahead depth is roughly $(d-1)/2$ tells us $d_l=2$ or 3 covers trees of depth 5–7, which is the range where interpretable trees are actually used. For $d_l=3$ we prune the candidate splits at each node to the top-$k$ by the first-round aggregate, following the top-$k$ lookahead idea of Blanc et al.. That costs one extra round per added level.
Relation to Prior Work
The closest existing work is FedGA-Tree, the only federated method in this file that searches over whole tree structures. Its server evolves tree skeletons with a genetic algorithm. Clients fit thresholds and leaves locally and return scalar fitness scores. It reports a 5.58% average F1 gain over local models. It also reports that a split-level differentially private greedy baseline did 2.58% worse than local models, which is the evidence this proposal builds on for the "privacy tax" of adding noise at every split.
This proposal keeps FedGA-Tree's two good instincts: send only aggregate losses, and personalize to each client. It changes everything else:
- Search method. FedGA-Tree searches stochastically over many rounds. Here the search is exact over a defined class and finishes in one or two rounds.
- What is shared and what is personalized. FedGA-Tree personalizes thresholds throughout the tree. Here personalization happens only below a shared top, which gives a common readable rule set at the root.
- Guarantees. Here the chosen top is provably optimal for the stated objective. FedGA-Tree offers no such guarantee.
The production federated tree systems play a different role. SecureBoost+, Federated Forest and HybridTree all grow trees greedily with node-by-node or layer-by-layer cryptographic exchange. All three target vertical or hybrid partitions, where parties hold different features, so they motivate the communication concern but are not direct competitors here.
HybridTree is closest in spirit. It shows that split order along a path can be rearranged with little loss, and it trains the top and bottom of a tree at different parties. Its segments are still grown greedily, whereas we optimize the top exactly.
The centralized global-optimization literature supplies the method and some constraints. SPLIT supplies the lookahead-plus-greedy decomposition, together with its evidence of near-optimality: 100–600x faster than the exact solver GOSDT, with test loss usually within 1%. Exact solvers such as van den Bos and Avellaneda show that full exact search does not scale past shallow depths. That rules out running full exact search in federation and is why we stop at $d_l$.
We deliberately do not build on Tree Alternating Optimization (TAO), which refines an existing tree by repeatedly re-fitting one node at a time, or on differentiable trees (GradTree, RADDT), which relax splits so the tree can be trained by gradient descent. TAO would need many rounds that each track which points' predictions depend on each node. GradTree relies on a straight-through gradient trick, and RADDT on a gradually sharpened soft routing (an annealing schedule). How either behaves under averaging across clients with different data is unknown and plausibly unstable, since averaging thresholds learned on different distributions can produce incoherent splits. RADDT also produces oblique splits, which combine several features and give up the axis-aligned readability that motivates this work.
Research Program
We will build the protocol in four stages.
- Shared thresholds. The thresholds come from a federated quantile sketch, so the $B$ bins per feature are agreed before search.
- Local computation. Each client enumerates all paths of length $d_l$ over the binned splits. For each path it runs a local CART completion to the remaining depth, using its own data and a local minimum-leaf-size rule, and records the resulting loss. Children are cached so that nodes shared by several paths are grown once.
- Aggregation. The loss vectors are combined by secure aggregation.
- Search. The server runs the SPLIT-style dynamic program over the aggregated table to select $T$, adding $\lambda$ per shared leaf.
For $d_l=3$ we add a second round, which evaluates only the top-$k$ candidate splits per node chosen in round one.
Analysis. We will prove that, given the aggregated table, the chosen top is optimal among binned depth-$d_l$ tops. We will also work out communication cost as a function of $p$, $B$, $d_l$ and $k$.
Privacy. We separate two threat levels.
- Semi-honest server. Secure aggregation alone means the server learns only the sum and the final tree.
- Differential privacy on the released top. The naive approach is to add noise to the whole table, but its sensitivity is high: one record falls into many paths. So we instead privatize the final selections themselves. We use a noisy-minimum selection at each of the $2^{d_l}-1$ shared nodes, where the score is aggregated completion loss with bounded 0–1 loss, plus the privatized quantile sketch.
The number of noisy releases therefore grows with the shared depth, not with the full depth. Whether this ordering interacts badly with the exactness of the dynamic program is an open question we will measure directly rather than assume away.
Non-IID stress. We will partition data with Dirichlet label skew and with covariate shift induced by a demographic attribute (for example, age bands on Adult). This tests the hypothesis that the per-client greedy bottoms absorb heterogeneity that would otherwise corrupt a single global tree.
Baselines
Naive reference: purely local CART. Each client fits a CART tree of the same total depth $d$ on its own data, with depth tuned on local validation. This is the "do nothing" point. FedGA-Tree's 5.58% average F1 gain over local models gives the scale of benefit federation can offer. We count as success a mean per-client F1 gain over local CART at least as large on shared datasets, together with a fraction of clients who benefit at least matching the 75% FedGA-Tree reports.
Strongest existing method: FedGA-Tree. We run it under the same client partitions, the same depth limit and participation rates, and a round budget matched to our total communicated bytes and to a generous multiple of our rounds. It is tuned by the same fixed hyperparameter-search budget we give our method. We compare on the Adult and Creditcard benchmarks it reports, plus Covtype, HELOC and COMPAS. Its published figures are relative to local models (5.58% average F1 improvement), and there is no reported per-dataset absolute result on Lacuna for FedGA-Tree on Covtype, HELOC or COMPAS. So all of its numbers here will be rerun. Beating it means higher mean client F1 at equal or fewer shared nodes, reached in far fewer rounds.
Split-level DP greedy trees. For the private regime we compare against a greedy tree with noise at every node, in the style of the IBM benchmark. FedGA-Tree reports this baseline 2.58% below local models. Beating it at matched privacy budget is a low bar, and we expect to clear it clearly.
Key ablation: shared greedy top plus local greedy bottoms. The top $d_l$ levels are chosen greedily from securely aggregated split statistics, and everything else is identical to our method, including thresholds, bottoms and privacy. This isolates the lookahead ingredient. Success means a statistically reliable reduction in total personalized loss and test error across datasets and seeds.
Structural ablation: a single global tree. A single global tree of depth $d$ chosen by the same lookahead, without per-client bottoms. This tests whether personalization is doing the work.
Reference points outside the method class. We report two ceilings. The first is centralized SPLIT on pooled data, extended to completions per client, as the "federation costs nothing" ceiling. The second is centralized XGBoost as an accuracy ceiling for non-interpretable models. There is no reported horizontal federated GBDT number on Lacuna for these datasets, so any comparison to federated ensembles would be run by us rather than quoted.
Why not just…?
Why not just grow the shared top greedily? This is the most serious threat, and it is exactly the key ablation above. SPLIT's premise is that greedy choices are worst at the root. That premise has been shown centrally, where the lookahead-completed tree matches the exact optimum. It has not been shown against a greedy top combined with personalized bottoms, and personalized bottoms might repair a bad root split on their own. If the greedy-top ablation matches our method within noise on most datasets, the honest conclusion is that federated personalization, not lookahead, carries the gain. We would then reframe the contribution around the one-shot protocol and its privacy accounting. We will also report where the two differ: specifically, datasets and skew levels where the greedy root split disagrees with the optimal one.
Why not just use FedGA-Tree with more generations? A genetic search can in principle find the same top. It gives no certificate that it has done so, however, and its cost is paid in communication rounds, which are the scarce resource in federation. Our experiment plots quality against rounds for both methods on matched partitions. The prediction is that our method reaches its optimum in one to two rounds, and FedGA-Tree either needs many more rounds to match it or never does. If FedGA-Tree matches us within the same round budget, exactness buys little in practice, and we will say so.
Why not just train local trees and skip federation? On small or skewed clients, local trees overfit and lack enough examples. FedGA-Tree's results and HybridTree's comparison against a party training alone both show federation helping. Our per-client breakdown will show whether gains concentrate in small clients, as expected, and whether any client is made worse off by adopting the shared top.
Why not just federate a differentiable tree with standard parameter averaging? GradTree's generalization gap (0.051 versus 0.183 for CART) is attractive, and averaging is simple. However, averaging thresholds learned on different client distributions has no guarantee of producing sensible splits, and RADDT's annealing schedule is fragile even centrally. We include federated-averaged GradTree as an exploratory baseline on the same partitions. If it wins under strong skew, that would argue for a hybrid in which the lookahead picks the structure and gradient steps tune the leaves.
Proposed Experiments and Decisive Checks
Datasets and setup. We use Adult, Creditcard, HELOC, COMPAS and Covtype. Adult and Creditcard are shared with FedGA-Tree, and HELOC, COMPAS and Covtype with SPLIT. Give-credit and Higgs serve as scalability stress tests. We vary the number of clients from 5 to 100, use Dirichlet concentration from 0.1 to 10, test participation down to 10% (matching FedGA-Tree's robustness test), and use total depth $d\in\{4,5,6,7\}$ with $d_l=\lfloor (d-1)/2\rfloor$.
Metrics. We measure mean and worst-client F1 and accuracy, number of shared and total nodes, bytes uploaded and rounds, and accuracy against the privacy budget $\varepsilon$ in the private regime.
Decisive checks. There are three.
- Our method must beat the greedy-top ablation at matched everything. Otherwise the lookahead claim fails.
- It must match or exceed FedGA-Tree's F1 in a fraction of its rounds.
- It must lose less accuracy under differential privacy than split-level noisy greedy trees, and show that the loss grows with $d_l$ rather than $d$.
Secondary check. A secondary check relates to HybridTree's finding that split rules recur across trees in over 90% of cases. We will test whether the optimal shared top stays stable across random client subsamples, which would support using it as a common, auditable rule set.
References
- Near-Optimal Decision Trees in a SPLIT Second
- Harnessing the power of choices in decision tree learning
- FedGA-Tree: Federated Decision Tree using Genetic Algorithm
- SecureBoost+: Large Scale and High-Performance Vertical Federated Gradient Boosting Decision Tree
- Federated Forest
- Effective and Efficient Federated Tree Learning on Hybrid Data
- Piecewise Constant and Linear Regression Trees: An Optimal Dynamic Programming Approach
- Efficient Inference of Optimal Decision Trees
- Alternating optimization of decision trees, with application to learning sparse oblique trees
- GradTree: Learning Axis-Aligned Decision Trees with Gradient Descent
- Differentiable Decision Tree via "ReLU+Argmin" Reformulation