論文の概要: BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height
- arxiv url: http://arxiv.org/abs/2610.10075v1
- Date: Wed, 07 Oct 2026 13:41:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 21:58:22.939328
- Title: BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height
- Title（参考訳）: BetweenCut: 木の高さに2つの対数誤差を持つプライベートヘビーノード分類
- Abstract要約: textscBetweenCutは、$(varepsilon,)$-DPアルゴリズムで、追加エラーマージンは$O_varepsilon,(loglog h)$で、深い木の既存の境界を改善します。
このエラーは全てのノードに対して同時に発生し、入力データベースのサイズとは独立している。
- 参考スコア（独自算出の注目度）: 27.791289171147906
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Finding heavy nodes in a tree---those whose counts exceed a given threshold---is a building block for analysis and learning over structured data. Achieving record-level differential privacy (DP) without sacrificing accuracy is challenging because each record contributes to counts along an entire root-to-leaf path, allowing privacy costs to accumulate across levels. Existing methods account for the multiple threshold comparisons for each record incur additive error margins of $Ω_{\varepsilon,δ}(\log h)$ or $Ω_{\varepsilon,δ}(\sqrt{\log h})$ for tree height $h$. We introduce \textsc{BetweenCut}, an $(\varepsilon,δ)$-DP algorithm with an additive error margin of $O_{\varepsilon,δ}(\log\log h)$, improving the existing bounds for deep trees. This error holds simultaneously for all nodes and is independent of the input database size.
- Abstract（参考訳）: ツリー内の重いノードを見つける - カウントが与えられたしきい値を超える - 構造データの解析と学習のためのビルディングブロックである。
記録レベルの差分プライバシー(DP)を精度を犠牲にすることなく達成することは、各レコードがルート・ツー・リーフパス全体に沿ってカウントに寄与するため、プライバシーコストがレベルを越えて蓄積されるため、困難である。
既存の方法は、木の高さが$h$に対して$Ω_{\varepsilon,δ}(\log h)$または$Ω_{\varepsilon,δ}(\sqrt{\log h})$の各レコードの複数のしきい値の比較を行う。
O_{\varepsilon,δ}(\log\log h)$ の付加誤差マージンを持つ $(\varepsilon,δ)$-DP アルゴリズムである \textsc{BetweenCut} を導入する。
このエラーは全てのノードに対して同時に発生し、入力データベースのサイズとは独立している。
関連論文リスト
- Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure [50.58119214447535]
マスク付き生成モデルは並列トークン予測を提供するが、正確な並列サンプリングはトークンを考慮しなければならない。
本研究は,発見を含む全評価がシーケンス長$N$のサブ線形であるかどうかを考察する。
本研究では, 森林構造を隠蔽した離散分布を, 固定された近似条件オラクルを通してアクセスする。
論文 参考訳（メタデータ） (2026-09-29T15:39:50Z) - The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting [18.604881105488513]
連続的数え上げのための微分プライベートなメカニズムはすべて、予想される$ell_infty$ error $(log3/2 n)$を発生しなければならないことを示す。
また、線形クエリに対して、遺伝的不一致とprivate $ell_infty$エラーを最大で分離する。
論文 参考訳（メタデータ） (2026-07-01T12:38:33Z) - High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。
我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
論文 参考訳（メタデータ） (2026-02-01T17:05:31Z) - Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model [61.40326886123332]
ターンタイルストリーミングモデルにおいて、異なる要素を数えるという根本的な問題に対して、最初のサブ線形空間を微分プライベートなアルゴリズムを与える。
本結果は, 線形問題である最先端アルゴリズムの空間要求を著しく改善する。
ストリームにアイテムが現れる回数の制限付き$W$が分かっている場合、我々のアルゴリズムは$tildeO_eta(sqrtW)$ space.sqrtW)$ additive errorを提供する。
論文 参考訳（メタデータ） (2025-05-29T17:21:20Z) - Differentially Private Kernel Density Estimation [11.526850085349155]
我々は、カーネル密度推定(KDE)のための洗練された微分プライベート(DP)データ構造を導入する。
類似関数 $f$ とプライベートデータセット $X サブセット mathbbRd$ が与えられた場合、我々のゴールは、任意のクエリ $yinmathbbRd$ に対して、X f(x, y)$ の $sum_x を微分プライベートな方法で近似するように$X$ を前処理することである。
論文 参考訳（メタデータ） (2024-09-03T08:01:19Z) - Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。
本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
論文 参考訳（メタデータ） (2022-09-09T08:54:13Z) - Active-LATHE: An Active Learning Algorithm for Boosting the Error
Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。
我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
論文 参考訳（メタデータ） (2021-10-27T10:45:21Z) - On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
我々は,アンサンブルスタンプの音響検証のための効率的なプログラムベースアルゴリズムを開発した。
我々は,アンサンブル・スタンプや木を訓練するための最初の認証された防御法を,$ell_p$ノルム摂動に関して実証した。
論文 参考訳（メタデータ） (2020-08-20T03:42:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。