PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable and Provably Accurate Algorithms for Differentially Private Distributed Decision Tree Learning

Kaiwen Wang, Travis Dick, Maria-Florina Balcan

arXiv:2012.10602v3cs.LGcs.CRstat.ML

TL;DR

Distributed decision-tree learning needs privacy-preserving methods that retain utility despite limited communication and information sharing. The paper introduces DP-TopDown with NoisyCounts and LocalRNM, proves utility guarantees, and reports that LocalRNM generally outperforms NoisyCounts while privacy and accuracy trade off across datasets.

  • Problem

    The paper addresses the lack of provably accurate differentially private top-down decision-tree algorithms for distributed data holders.

    Source: §1 · p. 2

  • Method

    DP-TopDown approximates optimal splits privately through PrivateSplit, with NoisyCounts aggregating noisy counts and LocalRNM performing local optimization.

    Source: §1 · p. 2

  • Results

    LocalRNM performs better than NoisyCounts on most datasets, while experiments illustrate privacy–accuracy trade-offs and utility guarantees hold with sufficient data.

    Source: §1 · p. 2, §3 · p. 5

  • Takeaways & Limitations

    The framework provides a starting point for scalable and provably accurate private decision-tree learning in distributed settings.

    Source: §5 · p. 9

    The distributed setting makes no assumptions about how data holders’ datasets are partitioned in size or distribution, and some implementations rely on finite |H|.

    Source: §2.3 · p. 4, §3 · p. 6

Abstract

from arXiv · show

This paper introduces the first provably accurate algorithms for differentially private, top-down decision tree learning in the distributed setting (Balcan et al., 2012). We propose DP-TopDown, a general privacy preserving decision tree learning algorithm, and present two distributed implementations. Our first method NoisyCounts naturally extends the single machine algorithm by using the Laplace mechanism. Our second method LocalRNM significantly reduces communication and added noise by performing local optimization at each data holder. We provide the first utility guarantees for differentially private top-down decision tree learning in both the single machine and distributed settings. These guarantees show that the error of the privately-learned decision tree quickly goes to zero provided that the dataset is sufficiently large. Our extensive experiments on real datasets illustrate the trade-offs of privacy, accuracy and generalization when learning private decision trees in the distributed setting.

1 Introduction

The paper addresses privacy barriers to distributed decision-tree learning by introducing DP-TopDown and two distributed implementations, with theoretical guarantees and empirical privacy–accuracy analysis.

1 Introduction

  • Private distributed learning is motivated by access to more diverse data, but privacy concerns can deter cooperation among data holders.Source: §1 · p. 1
  • Differential privacy quantifies information leakage, can encourage distributed learning with sensitive data, and is robust to post-processing.Source: §1 · p. 1

1.1 Related Works

  • Top-down trees remain attractive because their learned structure is more interpretable than deep neural networks, despite random forests sometimes outperforming them.Source: §1 · p. 2, §1.1 · p. 2

1 Introduction

  • NoisyCounts aggregates differentially private noisy counts, whereas LocalRNM performs local optimization to reduce communication and added noise.Source: §1 · p. 2
  • Experiments show LocalRNM performs better than NoisyCounts on most datasets while illustrating privacy–accuracy trade-offs and data-dependent generalization.Source: §1 · p. 2
  • DP-TopDown provides the first utility guarantees for private top-down decision-tree learning in both single-machine and distributed settings.Source: §1 · p. 2

1.1 Related Works

  • Prior work applied privacy mechanisms to specific top-down algorithms, while this work claims generalized utility guarantees and sample-complexity bounds, including for distributed learning.Source: §1.1 · p. 2

2 Preliminaries

The preliminaries define top-down decision-tree learning, differential privacy mechanisms, and the distributed setting that DP-TopDown must support.

2.1 Top-down Decision Tree Learning

  • TopDown repeatedly selects a leaf and splitting function that maximally decreases an error upper bound, then labels final leaves by their majority class.Source: §2.1 · p. 3
  • The splitting criterion upper-bounds tree error, and each split is scored by the potential decrease w(ℓ)J(ℓ,h).Source: §2.1 · p. 3
  • Under the Weak Learning Assumption, entropy-based TopDown reaches training error at most ε after (1/ε)O(log(1/ε)/γ^2) splits.Source: §2.1 · p. 4

2.2 Differential Privacy

  • Differential privacy protects neighboring datasets, while the Laplace mechanism releases a function plus noise calibrated to sensitivity and privacy parameter α.Source: §2.2 · p. 4
  • Report Noisy Max privately selects the highest-scoring candidate and can add less noise than applying separate Laplace mechanisms to every score.Source: §2.2 · p. 4
  • Repeated private mechanisms remain differentially private through standard composition theorems.Source: §2.2 · p. 4

2.3 Distributed Setting with Privacy Constraints

  • The distributed model gives each data holder privacy for its local data without assuming how holders’ datasets differ in size or distribution.Source: §2.3 · p. 4
  • This setting differs from local differential privacy because patient data are protected when queried outside the hospital rather than perturbed before hospital access.Source: §2.3 · p. 4

3 Differentially Private TopDown

DP-TopDown privatizes top-down split selection through PrivateSplit, with privacy-budget allocation and utility guarantees that apply to single-machine and distributed learning. NoisyCounts provides a distributed noisy-counts implementation, while LocalRNM reduces query noise and communication but lacks general utility guarantees.

DP-TopDown

  • DP-TopDown encapsulates private split selection in PrivateSplit, whose privacy and near-optimality requirements support the algorithm’s privacy and utility analysis.PrivateSplit outputs a split while preserving α-differential privacy and, with enough data at a leaf, approximates the best split with high probability.Source: §3 · pp. 4–5

Privacy budgeting

  • Uniform budgeting splits privacy across depths, whereas decay budgeting assigns B(d) = 1/2d and tends to yield higher accuracy by emphasizing earlier splits.The total depth budget must remain bounded, and the privacy allocation also trades off internal splitting against leaf labeling.Source: §3 · p. 5

Utility guarantee

  • Theorem 3 guarantees training error ≤ε with probability ≥1 −δ after (1/ε)O(log(1/ε)/γ2) splits under the Weak Learning Assumption and sufficient data.The proof controls estimated leaf weights and ensures PrivateSplit receives enough data to preserve a substantial fraction of the non-private potential reduction.Source: §3 · pp. 5–6

Distributed setting

  • In distributed learning, leaf weights and labels can be estimated from noisy counts, with leaf labeling selecting the maximum aggregated label count.Distributed leaf labeling adds a k factor to the sample complexity, after which a distributed PrivateSplit enables DP-TopDown.Source: §3 · p. 7

NoisyCounts

  • NoisyCounts has sample requirement |S| ≥eO(M 3k|H|/(ε2γ2α)) under uniform budgeting because every entity publishes noisy counts for every splitting function.Compared with the single-machine setting, the additional k|H| factor reflects distributed aggregation across entities and all candidate splits.Source: §3 · pp. 7–8

LocalRNM

  • LocalRNM lets each entity privately select its locally best split, then runs NoisyCounts over only those candidates, reducing query noise from |H| to k.This heuristic lacks general PrivateSplit utility guarantees because locally best splits from small datasets may perform poorly globally, but it outperformed NoisyCounts on four of seven datasets.Source: §3 · p. 8

4 Experimental Evaluation

Experiments on seven datasets evaluate DP-TopDown's privacy-accuracy trade-offs, budgeting choices, and sensitivity to training-set size. LocalRNM generally outperforms NoisyCounts in distributed experiments, while privacy noise can sometimes improve generalization.

Experimental setup

  • The experiments cover seven datasets with dataset-specific threshold-based splitting classes, four uniformly random data holders, and 100 independent runs.Entropy splitting used M = 512, ε = 0.1, and α ∈ {2^-3, 2^-2, ..., 2^9}.Source: §4 · pp. 8–9

Budgeting trade-offs

  • Fixing LPF = 0.5 balances privacy allocated to leaf labeling and internal splits after performance deteriorates near either extreme.Decay budgeting is more sensitive to noisy leaf labels when LPF approaches 0.Source: §4 · p. 9

Privacy-accuracy trade-offs

  • LocalRNM consistently outperforms NoisyCounts on Adult, Bank, Creditcard, and Skin, while single-machine DP-TopDown performs best overall.As α increases, private accuracy converges toward the non-private baseline.Source: §4 · p. 9

Generalization effects

  • Private algorithms outperform non-private trees on CTR for some α because small noise can avoid unlucky greedy choices and improve test accuracy.The result exposes a trade-off among privacy, accuracy, and generalization.Source: §4 · p. 9

Training-set size

  • Larger training sets consistently improve test accuracy, whereas smaller sets produce higher variance because injected noise has greater relative effect on queries.For small datasets, NoisyCounts privacy curves can outperform non-private baselines.Source: §4 · p. 9
  • Larger datasets also produce higher training accuracy, despite smaller datasets being easier to overfit.This pattern is reported in the training-accuracy analogue of the privacy curves.Source: §4 · p. 9

5 Conclusion

The paper unifies theory and practice for differentially private top-down decision-tree learning in distributed settings. It reduces private learning to approximating optimal splits with PrivateSplit and supports the approach with utility guarantees and experiments.

5 Conclusion

  • The paper provides the first utility guarantees for differentially private top-down decision-tree learning in the distributed setting and evaluates the algorithms on seven datasets.The conclusion presents the work as a unified theoretical and experimental treatment.Source: §5 · p. 9
  • DP-TopDown reduces private top-down learning to the key challenge of approximating optimal splits with PrivateSplit.Theorem 3 can provide utility guarantees for other PrivateSplit implementations.Source: §5 · p. 9
  • Figure 3 compares test accuracy against α for training sets of different sizes, using solid non-private baselines and dotted noised runs.A 0.01 curve represents training on a random 1% subset of the total dataset.Source: Figure 3 · p. 10

A.1 Composition Theorems of Differential Privacy

The composition theorems specify how privacy parameters combine when multiple differentially private mechanisms are applied. Sequential composition adds privacy losses, whereas parallel composition takes the maximum over disjoint partitions.

A.1 Composition Theorems of Differential Privacy

  • Sequential composition gives the combined mechanism (Σ_i α_i)-differential privacy when k mechanisms satisfy α_i-differential privacy.The mechanism may choose each later mechanism based on previous outputs.Source: §A.1 · p. 12
  • Parallel composition gives max_i α_i-differential privacy when mechanisms operate on disjoint partitions of the input domain.Each mechanism receives the data restricted to its corresponding partition.Source: §A.1 · p. 12

A.2 Sensitivity of Entropy

The entropy-sensitivity analysis bounds how much the split-quality objective J can change between neighboring datasets. This bound supports the use of randomized response or noise-based selection in PrivateSplit.

A.2 Sensitivity of Entropy

  • The analysis formulates J(S, h) over a dataset S, which generalizes the leaf-specific objective J(ℓ, h) used for a tree leaf.This notation is used to derive the global sensitivity needed by PrivateSplit with RNM.Source: §A.2 · p. 13
  • For the entropy function G(q) = −q lg(q) − (1 − q) lg(1 − q), the sensitivity of J(S, h) on a dataset of size m is bounded by 2/m.The result applies to any splitting function h.Source: §A.2 · p. 13
  • The proof compares label and branch counts for neighboring datasets, where each count changes by at most one.It uses a standard logarithmic inequality and the monotonicity of −x log(x) on the stated range.Source: §A.2 · p. 13

A.3 RNM Implements SingleMachine PrivateSplit

The single-machine RNM procedure privately selects nearly optimal splits by adding Laplace noise to split scores, with utility guarantees once each leaf has enough data.

A.3 RNM Implements SingleMachine PrivateSplit

  • RNM adds Laplace noise to each split score and privately selects the split with the largest noisy score.The procedure preserves α-differential privacy and returns the maximizing index over noisy scores.Source: §A.3 · p. 13
  • With sufficiently large leaf samples, the selected split is ζ-optimal and its estimated score differs from the true score by at most ζ with probability at least 1 −δ.Theorem 14 establishes both guarantees for the single-machine RNM-based procedure.Source: §A.3 · p. 13
  • The utility proof controls all score perturbations simultaneously by bounding Laplace noise and applying a logarithmic sample-size condition.The argument uses Lemma 12 for noise concentration and Lemma 13 to obtain the required sample size.Source: §A.3 · pp. 13–14
  • The resulting sample complexity is expressed as N(ζ, α, δ) with dependence on the hypothesis-class size and privacy and failure parameters.The supplied derivation gives the asymptotic form but truncates part of the displayed expression.Source: §A.3 · p. 14

A.4 NoisyCounts Implements Distributed PrivateSplit

NoisyCounts implements distributed PrivateSplit by having entities release noisy counts that the coordinator aggregates into split scores, preserving privacy while retaining utility guarantees.

A.4 NoisyCounts Implements Distributed PrivateSplit

  • NoisyCounts adds Laplace noise to distributed estimates of label-and-split counts, which the coordinator sums to compute each noisy split score.Each count receives a privacy-budgeted Laplace perturbation before aggregation.Source: §A.4 · p. 14
  • The entire distributed count-release operation preserves α-differential privacy.Privacy follows from the Laplace mechanism and the stated composition argument.Source: §A.4 · p. 14
  • With enough samples, NoisyCounts selects a ζ-near-optimal split and estimates its score within ζ with probability at least 1 −δ.Theorem 15 provides these guarantees for the distributed procedure.Source: §A.4 · p. 14
  • The analysis treats each aggregated count as the true count plus a sum of independent Laplace noises and bounds that sum with high probability.This produces the stated error control for all candidate split scores.Source: §A.4 · p. 14
  • The distributed sample complexity scales with the number of entities and the hypothesis-class size through the derived N(ζ, α, δ) bound.The supplied expression is asymptotically stated in terms of k and |H|.Source: §A.4 · p. 14

A.5 Proof of Main Theorem 3

The main theorem shows that DP-TopDown achieves low training error under a weak learning assumption when private split selection, weight estimation, and leaf labeling receive sufficient data.

A.5 Proof of Main Theorem 3

  • Under the Weak Learning Assumption with advantage γ, DP-TopDown reaches training error at most ε after (1/ε)O(log(1/ε)/γ^2) splits with probability at least 1 −δ.The dataset-size requirement depends on the privacy-budget schedule and the PrivateSplit data requirement.Source: §A.5 · p. 14
  • The proof separately controls private split calls, weight estimates, and leaf-labeling errors, then combines them with a union bound.There are at most 2M + 1 PrivateSplit calls, and the leaf and weight conditions are allocated failure probabilities across the proof.Source: §A.5 · p. 15
  • The queue contains a sufficiently large leaf for splitting because weak learning guarantees a leaf with enough weighted impurity, while queued leaves have nontrivial weight.This ensures the PrivateSplit sample requirement is met when the overall dataset is large enough.Source: §A.5 · p. 15
  • Each iteration reduces the tree potential according to a recurrence inherited from weak-learning analysis, provided the private split is sufficiently accurate.Choosing ζ appropriately yields the recurrence used to derive the split bound.Source: §A.5 · pp. 14–15
  • The same style of analysis also applies to the splitting criteria G(q) = 4q(1 −q) and G(q) = 2q(1 −q).Source: §A.5 · p. 16
  • In the distributed setting, weight estimation and leaf labeling use local Laplace mechanisms, introducing an additional k-dependent factor into the sample complexity.The distributed analysis bounds sums of k independent noises and identifies the resulting k factor.Source: §A.5 · p. 16

A.6 Splitting Classes for MNIST and Avazu CTR

The appendix specifies task-specific splitting classes and reports how budgeting, dataset size, tree structure, and splitting criteria affect private decision-tree behavior.

A.6 Splitting Classes for MNIST and Avazu CTR

  • MNIST uses three intensity thresholds per 4 × 4 image block, while Avazu CTR uses feature-specific threshold counts ranging from 4 to 100.The MNIST thresholds operate on averaged block pixels; Avazu thresholds vary across C1, C14–C21 features.Source: §A.6 · p. 16

A.7 More Experimental Results for Figure 1

  • Test accuracy is generally highest at interior LPF values, but the effect of LPF varies substantially across datasets, algorithms, privacy levels, and budgeting strategies.For LocalRNM on KDDCup, decay budgeting at α = 8.0 and α = 1.0 improved markedly when LPF decreased to 0.5.Source: §A.7 · p. 16, Figure 4 · p. 17

A.8 More Experimental Results for Figure 2

  • Lower privacy budgets produce shallower and smaller trees; NoisyCounts consistently learns the deepest trees, whereas LocalRNM learns the shallowest.These results are reported for training accuracy, tree depth, and tree size under the Figure 2 setup.Source: §A.8 · pp. 16, 18, Figure 5 · p. 20

A.9 More Experimental Results for Figure 3

  • Larger training sets improve private training accuracy enough to outweigh the higher training accuracy that small baseline datasets obtain through overfitting.The same positive dataset-size trend appears in testing accuracy, while private models on smaller datasets remain less accurate.Source: §A.9 · p. 18, Figure 6 · p. 21

A.10 Sensitivity of Other Splitting Criteria

  • Entropy sample-complexity bounds also apply to Gini and Root Gini because their score sensitivities remain of order eO(1/m).The appendix derives sensitivities for both criteria before stating this transfer of bounds.Source: §A.10 · pp. 18–19
Loading 2012.10602v3…