論文の概要: Instance-Optimality for Private KL Distribution Estimation
- arxiv url: http://arxiv.org/abs/2505.23620v1
- Date: Thu, 29 May 2025 16:27:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-30 18:14:07.986426
- Title: Instance-Optimality for Private KL Distribution Estimation
- Title（参考訳）: プライベートKL分布推定のためのインスタンス最適性
- Authors: Jiayuan Ye, Vitaly Feldman, Kunal Talwar,
- Abstract要約: 未知の離散分布 $p$ over $d$ symbols, given $n$ i.i.d. sample from the distribution。
本稿では,差分プライバシー制約を伴わずに,一定要素までのインスタンス最適化を実現するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 41.35506763248454
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We study the fundamental problem of estimating an unknown discrete distribution $p$ over $d$ symbols, given $n$ i.i.d. samples from the distribution. We are interested in minimizing the KL divergence between the true distribution and the algorithm's estimate. We first construct minimax optimal private estimators. Minimax optimality however fails to shed light on an algorithm's performance on individual (non-worst-case) instances $p$ and simple minimax-optimal DP estimators can have poor empirical performance on real distributions. We then study this problem from an instance-optimality viewpoint, where the algorithm's error on $p$ is compared to the minimum achievable estimation error over a small local neighborhood of $p$. Under natural notions of local neighborhood, we propose algorithms that achieve instance-optimality up to constant factors, with and without a differential privacy constraint. Our upper bounds rely on (private) variants of the Good-Turing estimator. Our lower bounds use additive local neighborhoods that more precisely captures the hardness of distribution estimation in KL divergence, compared to ones considered in prior works.
- Abstract（参考訳）: 未知の離散分布 $p$ over $d$ symbols, given $n$ i.i.d. sample from the distribution。
我々は、真の分布とアルゴリズムの推定とのKLのばらつきを最小化することに興味がある。
まず、ミニマックス最適プライベート推定器を構築する。
しかし、minimaxの最適性は、個々の(Worst-case)インスタンス上でのアルゴリズムの性能に光を当てることに失敗し、単純なminimax-Optimal DP 推定器は実分布において経験的性能が劣る可能性がある。
次に、この問題をインスタンス最適化の観点から研究し、p$上のアルゴリズムの誤差を、p$の小さな局所的近傍における最小到達可能な推定誤差と比較する。
局所地区の自然概念の下では, 差分プライバシー制約を伴わずに, 一定要素までのインスタンス最適性を達成できるアルゴリズムを提案する。
我々の上界はグッドチューリング推定器の(プライベートな)変種に依存している。
我々の下限は、KL分散における分布推定の硬さをより正確に捉えた付加的な局所近傍を用いている。
関連論文リスト
- Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。
多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
論文 参考訳（メタデータ） (2024-09-08T13:08:45Z) - Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond $1+\alpha$ Moments [10.889739958035536]
本稿では,アルゴリズムの微細な最適性を分析するための新しい定義フレームワークを提案する。
平均値の中央値は近傍最適であり, 一定の要因が得られている。
定数係数のずれのない近傍分離推定器を見つけることは自由である。
論文 参考訳（メタデータ） (2023-11-21T18:50:38Z) - Simple Binary Hypothesis Testing under Local Differential Privacy and
Communication Constraints [8.261182037130407]
局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。
我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
論文 参考訳（メタデータ） (2023-01-09T18:36:49Z) - Instance-Optimal Differentially Private Estimation [2.320417845168326]
我々は,$epsilon$-differential privacyの対象となる局所最小収束推定値について検討した。
そこで本研究では,Canonneらの最近の最適プライベートテスタによる簡易仮説テストのための最適アルゴリズムが,局所最小推定アルゴリズムの設計を直接的に通知することを示した。
論文 参考訳（メタデータ） (2022-10-28T01:08:01Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Robust Learning of Optimal Auctions [84.13356290199603]
本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。
我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-07-13T17:37:21Z) - Optimal Rates of (Locally) Differentially Private Heavy-tailed
Multi-Armed Bandits [11.419534203345187]
本稿では,DP/LDPモデルにおけるマルチアームバンディット(MAB)の問題について検討する。
本稿では,SEアルゴリズムの局所的プライベートかつロバストなバージョンとみなすアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-04T16:17:21Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Learning Minimax Estimators via Online Learning [55.92459567732491]
確率分布のパラメータを推定するミニマックス推定器を設計する際の問題点を考察する。
混合ケースナッシュ平衡を求めるアルゴリズムを構築した。
論文 参考訳（メタデータ） (2020-06-19T22:49:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。