論文の概要: Optimal Best Arm Identification under Differential Privacy
- arxiv url: http://arxiv.org/abs/2510.17348v1
- Date: Mon, 20 Oct 2025 09:46:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-25 00:56:39.388777
- Title: Optimal Best Arm Identification under Differential Privacy
- Title（参考訳）: 微分プライバシー下での最適腕識別
- Authors: Marc Jourdan, Achraf Azize,
- Abstract要約: BAI(Best Arm Identification)アルゴリズムは、適応的な臨床試験やユーザリサーチなど、データに敏感なアプリケーションにデプロイされる。
本研究では,ベルヌーイ分布に対するグローバル微分プライバシー(DP)の下での固定信頼度BAIの問題について検討する。
提案アルゴリズムは,既存の$delta$correctおよび$epsilon$-global DP BAIアルゴリズムより,$epsilon$の異なる値に対して優れている。
- 参考スコア（独自算出の注目度）: 8.321992395325912
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Best Arm Identification (BAI) algorithms are deployed in data-sensitive applications, such as adaptive clinical trials or user studies. Driven by the privacy concerns of these applications, we study the problem of fixed-confidence BAI under global Differential Privacy (DP) for Bernoulli distributions. While numerous asymptotically optimal BAI algorithms exist in the non-private setting, a significant gap remains between the best lower and upper bounds in the global DP setting. This work reduces this gap to a small multiplicative constant, for any privacy budget $\epsilon$. First, we provide a tighter lower bound on the expected sample complexity of any $\delta$-correct and $\epsilon$-global DP strategy. Our lower bound replaces the Kullback-Leibler (KL) divergence in the transportation cost used by the non-private characteristic time with a new information-theoretic quantity that optimally trades off between the KL divergence and the Total Variation distance scaled by $\epsilon$. Second, we introduce a stopping rule based on these transportation costs and a private estimator of the means computed using an arm-dependent geometric batching. En route to proving the correctness of our stopping rule, we derive concentration results of independent interest for the Laplace distribution and for the sum of Bernoulli and Laplace distributions. Third, we propose a Top Two sampling rule based on these transportation costs. For any budget $\epsilon$, we show an asymptotic upper bound on its expected sample complexity that matches our lower bound to a multiplicative constant smaller than $8$. Our algorithm outperforms existing $\delta$-correct and $\epsilon$-global DP BAI algorithms for different values of $\epsilon$.
- Abstract（参考訳）: BAI(Best Arm Identification)アルゴリズムは、適応的な臨床試験やユーザリサーチなど、データに敏感なアプリケーションにデプロイされる。
これらのアプリケーションのプライバシに関する懸念から,Bernolliディストリビューションのグローバル差分プライバシー(DP)の下での固定信頼型BAIの問題について検討する。
多くの漸近的に最適なBAIアルゴリズムが非プライベートな設定に存在しているが、グローバルDP設定の最高下限と上限の間には大きなギャップが残っている。
この作業により、プライバシー予算が$\epsilon$の場合、このギャップを小さな乗法定数に縮める。
まず、$\delta$-correct と $\epsilon$-global DP 戦略の期待されるサンプル複雑性により強い制約を与える。
我々の下限は、非私的特性時間で使用される輸送コストのクルバック・リブラー(KL)偏差を、KL偏差とトータル変分距離を$\epsilon$で最適に交換する新しい情報理論量に置き換える。
第2に、これらの輸送コストに基づく停止規則と、アーム依存の幾何学的バッチリングを用いて計算された手段のプライベートな推定法を導入する。
停止規則の正しさを証明するために、ラプラス分布とベルヌーイ分布とラプラス分布の和に対する独立な関心の集中結果を導出する。
第3に、これらの輸送コストに基づくトップ2サンプリングルールを提案する。
任意の予算$\epsilon$に対して、予想されるサンプルの複雑さの漸近上界を示し、それは我々の下界と8ドル以下の乗法定数に一致する。
我々のアルゴリズムは、既存の$\delta$-correctおよび$\epsilon$-global DP BAIアルゴリズムを、$\epsilon$の異なる値に対して上回る。
関連論文リスト
- Optimal Regret of Bernoulli Bandits under Global Differential Privacy [44.25744563135375]
エプシロン$-global Differential Privacy (DP) による包帯のレグレット最小化が広く研究されている。
我々はベルヌーイのバンディットに対する$epsilon-global DPアルゴリズムの残酷な下限と上限を再検討し、両者を改善した。
論文 参考訳（メタデータ） (2025-05-08T19:48:58Z) - Differentially Private Best-Arm Identification [14.916947598339988]
ベストアーム識別(BAI)問題は、データセンシティブなアプリケーションに徐々に使われている。
これらのアプリケーションによって引き起こされるデータプライバシの懸念に触発され、ローカルモデルと中央モデルの両方に一定の信頼を保ちながら、BAIの問題を研究する。
論文 参考訳（メタデータ） (2024-06-10T16:02:48Z) - Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。
我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
論文 参考訳（メタデータ） (2024-05-30T18:20:35Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。
純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。
平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
論文 参考訳（メタデータ） (2022-12-15T18:27:39Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - 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) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。