論文の概要: Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees

• arxiv url: http://arxiv.org/abs/2605.22756v1
• Date: Thu, 21 May 2026 17:23:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-22 16:35:42.371868
• Title: Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees
• Title（参考訳）: Lumberjack: 樹木の重度ヒッタ検出による、より分化した私有林
• Authors: Christian Janos Lebeda, David Erb, Tudor Cebere, Aurélien Bellet,
• Abstract要約: Lumberjackは差分的にプライベートなランダムフォレストアルゴリズムで、実用性を大幅に向上する。 我々のアプローチの重要な構成要素は、階層データに対する新しい$(varepsilon,)$-DP重み検出アルゴリズムである。 Lumberjackは従来のDPランダムフォレスト法よりも優れていた。
• 参考スコア（独自算出の注目度）: 13.259647860047982
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random forests are widely used in fields involving sensitive tabular data, but existing approaches to enforcing differential privacy (DP) typically degrade performance to the point of impracticality. In this paper, we introduce Lumberjack, a differentially private random forest algorithm that achieves substantially higher utility by constructing large random decision trees and then applying aggressive, privacy-preserving pruning to retain only sufficiently populated nodes. A key component of our approach is a novel $(\varepsilon,δ)$-DP heavy hitter detection algorithm for hierarchical data, whose error is $O_{\varepsilon,δ}(\sqrt{\log h})$ for trees of height $h$ and may be of independent interest. This favorable scaling enables the use of significantly deeper trees than in prior work, leading to improved expressiveness under privacy constraints. Our empirical evaluation on benchmark datasets shows that Lumberjack consistently outperforms prior DP random forest methods, establishing a new state of the art. In particular, our approach yields substantial improvements in the privacy-utility trade-off for practical privacy budgets. Our findings suggest that carefully designed DP random forests can close much of the utility gap, highlighting a promising and underexplored direction for future research.
• Abstract（参考訳）: ランダムフォレストは、センシティブな表層データを含むフィールドで広く利用されているが、差分プライバシー(DP)を強制する既存のアプローチは、通常、パフォーマンスを非現実的な点まで低下させる。 本稿では,大きなランダムな決定木を構築して,十分なノードのみを保持するために,攻撃的かつプライバシ保護プルーニングを適用して,極めて高いユーティリティを実現する,差分プライベートなランダムフォレストアルゴリズムであるLumberjackを紹介する。 このアプローチの重要なコンポーネントは、階層データに対する新しい$(\varepsilon,δ)$-DP重ヒッタ検出アルゴリズムで、エラーは$O_{\varepsilon,δ}(\sqrt{\log h})$で、高さが$h$のツリーに対しては$O_{\varepsilon,δ}(\sqrt{\log h})$である。 この好ましいスケーリングにより、以前の作業よりもはるかに深いツリーの使用が可能になり、プライバシ制約下での表現性の向上につながります。 Lumberjackは従来のDPランダムフォレスト手法より一貫して優れており,新たな最先端の手法が確立されている。 特に、我々のアプローチは、実用的なプライバシー予算のためのプライバシーユーティリティトレードオフを大幅に改善する。 以上の結果から,DPランダム林はユーティリティーギャップの大部分を埋めることが可能であり,今後の研究にとって有望で未発見の方向を示すことが示唆された。

関連論文リスト

• Entropy-Tree: Tree-Based Decoding with Entropy-Guided Exploration [52.52685988964061]
  Entropy-Treeは、分岐決定の信号としてエントロピーを利用するツリーベースのデコード手法である。 単一の復号処理において、効率的な構造化された探索と信頼性の高い不確実性推定を統一する。
  論文  参考訳（メタデータ） (2026-01-02T07:14:05Z)
• DiNo and RanBu: Lightweight Predictions from Shallow Random Forests [2.2080796858692575]
  DiNoとRanBuは、小さな深度制限木を効率的な距離重み付き予測子に変換する。 RanBuは、ハイノイズ設定で、完全奥行きのランダムな森の精度を一致または超過する。 どちらの手法も量子レグレッションに直接拡張し、精度を相当なスピードゲインで維持する。
  論文  参考訳（メタデータ） (2025-10-23T20:12:08Z)
• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  ユーザレベルの差分プライベート凸最適化(DP-SCO)は、マシンラーニングアプリケーションにおけるユーザのプライバシ保護の重要性から、大きな注目を集めている。 微分プライベート勾配勾配(DP-SGD)に基づくような現在の手法は、しばしば高雑音蓄積と準最適利用に苦しむ。 これらの課題を克服するために、ロバストな統計、特に中央値とトリミング平均を利用する新しい線形時間アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-02-13T02:05:45Z)
• Adaptive Split Balancing for Optimal Random Forest [8.916614661563893]
  そこで本研究では,新しい適応型分割バランス法を用いて木を構築するランダムフォレストアルゴリズムを提案する。 本手法は,データから木構造を適応的に学習しながら,シンプルでスムーズなシナリオで最適性を実現する。
  論文  参考訳（メタデータ） (2024-02-17T09:10:40Z)
• Differentially-Private Decision Trees and Provable Robustness to Data Poisoning [8.649768969060647]
  決定木は非線形学習問題に適した解釈可能なモデルである。 この目的のための現在の最先端のアルゴリズムは、小さなプライバシー上の利益のために多くのユーティリティを犠牲にしている。 プライバトレーは個人のヒストグラムに基づいて、小さなプライバシー予算を消費しながら、良好な分割を選択する。
  論文  参考訳（メタデータ） (2023-05-24T17:56:18Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。 DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
  論文  参考訳（メタデータ） (2022-06-27T03:45:02Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)
• A One-Pass Private Sketch for Most Machine Learning Tasks [48.17461258268463]
  差別化プライバシ(DP)は、正式な証明可能な保証を通じて、プライバシとユーティリティのトレードオフを説明する魅力的なプライバシ定義である。 本稿では,回帰,分類,密度推定など,多数の機械学習タスクをサポートするプライベートスケッチを提案する。 このスケッチは,局所性に敏感なハッシュをインデックス化して,効率的なワンパスアルゴリズムで構築したランダムな一致テーブルで構成されている。
  論文  参考訳（メタデータ） (2020-06-16T17:47:48Z)
• Balance is key: Private median splits yield high-utility random trees [4.90655427233754]
  本研究では,ディプリメ林(DiPriMe forests)を提案する。 理論的かつ実証的に、結果のアルゴリズムは、差分プライバシーを確保しつつ、高い実用性を示すことを示す。
  論文  参考訳（メタデータ） (2020-06-15T21:59:30Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。