論文の概要: Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy
- arxiv url: http://arxiv.org/abs/2610.04600v1
- Date: Sat, 03 Oct 2026 15:38:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 02:58:29.320505
- Title: Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy
- Title（参考訳）: 差分プライバシー下での固定予算を用いた漸近的最適腕同定
- Abstract要約: 我々は、純粋な$$差分プライバシーの下で、盗賊に対する固定予算のベスト・アーム識別について検討する。
本稿では,Laplace-tree機構を用いてプライベートランニング推定を行う適応アルゴリズムAO-Pri-BAIを提案する。
数値的研究により、AO-Pri-BAIは非漸近的な設定でもベンチマークアルゴリズムより優れていることが示された。
- 参考スコア（独自算出の注目度）: 46.582768419539434
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Best arm identification under differential privacy is a pure-exploration problem in which both statistical efficiency and privacy protection must be achieved simultaneously. We study fixed-budget best arm identification for bandits under pure $ε$-differential privacy, where the learner must recommend an arm after a prescribed sampling budget while protecting the full transcript. We prove that the optimal exponential decay rate of the error probability is upper bounded by an instance-dependent privacy-aware transportation exponent that differs from the analogous quantity used to characterize the stopping time in fixed-confidence analysis by Jourdan and Azize [2025]. Guided by this exponent, we propose AO-Pri-BAI, an adaptive algorithm that maintains private running estimates through Laplace-tree mechanisms and learns a sampling design through a min--max interaction between hard alternatives and arm allocations. We prove that AO-Pri-BAI satisfies pure $ε$-differential privacy. We also establish that the exponent of the failure probability of AO-Pri-BAI matches the privacy-aware benchmark. Numerical studies show that even in the non-asymptotic setting, AO-Pri-BAI outperforms benchmark algorithms on various instances, complementing the theoretical analyses.
- Abstract（参考訳）: 差分プライバシーの下での最高の腕識別は、統計効率とプライバシー保護の両方を同時に達成しなければならない純粋探索問題である。
本研究は,純$ε$差分プライバシに基づく盗賊の固定予算ベスト腕識別について検討し,学習者は本書の全文を保護しながら,所定のサンプリング予算の後に腕を推薦しなければならない。
本稿では,Jourdan と Azize [2025] による固定信頼分析における停止時間を特徴付ける類似量とは異なる,インスタンス依存のプライバシ対応輸送指数によって,エラー確率の最適指数的減衰率を上限とすることを示す。
この指数によって導かれる適応アルゴリズムであるAO-Pri-BAIを提案する。これはLaplace-tree機構を通じてプライベートランニング推定を保守し、ハードオルタナティブとアームアロケーション間のmin-max相互作用によってサンプリング設計を学習する。
AO-Pri-BAIが純粋な$ε$-差分プライバシーを満足していることを証明する。
また,AO-Pri-BAIの故障確率指数は,プライバシを意識したベンチマークと一致していることを確認した。
数値的研究により、AO-Pri-BAIは漸近的でない環境でも、様々なケースでベンチマークアルゴリズムを上回り、理論解析を補完することを示した。
関連論文リスト
- Beyond Data Splitting: Full-Data Conformal Prediction by Differential Privacy [5.19945480121051]
既存のプライベートアプローチは、しばしばデータ分割に依存し、効果的なサンプルサイズを減らす。
分割を回避した完全データのプライバシ保存型コンフォメーション予測フレームワークを提案する。
一般的な差分プライバシー保証は、普遍的なカバレッジフロアをもたらすが、一般的には1ドルから1ドル程度のレベルを回復することはできない。
論文 参考訳（メタデータ） (2026-03-08T08:25:16Z) - High-Probability Bounds For Heterogeneous Local Differential Privacy [6.092107731520248]
局所差分プライバシー(LDP)に基づく統計的推定について検討する。
我々は、少なくとも1-βの確率を保持するような$ell$-normの有限サンプル上限を開発する。
我々はさらに$ell_infty$-distanceで分布学習を研究し、不均一なプライバシー要求の下で高い確率保証を持つアルゴリズムを設計する。
論文 参考訳（メタデータ） (2025-10-13T19:54:44Z) - DP-NCB: Privacy Preserving Fair Bandits [7.443474354626665]
そこで我々は,DP-NCB(Disfferially Private Nash Confidence Bound)という新しいアルゴリズムフレームワークを紹介した。
同時に$epsilon$-differentialのプライバシを保証し、既知の下位境界を対数的要素まで一致させて、オーダー最適化のNash後悔を実現する。
われわれの結果は、プライバシー保護と公正の両方を兼ね備えた帯域幅アルゴリズムを設計するための原則的な基盤を提供する。
論文 参考訳（メタデータ） (2025-08-05T18:34:00Z) - Breaking the Gaussian Barrier: Residual-PAC Privacy for Automatic Privatization [27.430637970345433]
PACプライバシーアルゴリズムによって得られる上限は、摂動機構の出力が独立雑音を伴うガウス的である場合にのみ厳密であることを示す。
本稿では,逆推定後に残るプライバシを定量化するf-divergenceベースの尺度であるResidual-PAC(R-PAC)プライバシーを紹介する。
提案手法は,任意のデータ分布に対する効率的なプライバシ予算利用を実現し,複数のメカニズムがデータセットにアクセスすると自然に構成する。
論文 参考訳（メタデータ） (2025-06-06T20:52:47Z) - Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。
我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
論文 参考訳（メタデータ） (2025-06-03T02:56:26Z) - Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - On the Complexity of Differentially Private Best-Arm Identification with
Fixed Confidence [16.295693624977563]
我々は、$epsilon$-global Differential Privacyの下で、信頼度を固定したベストアーム識別の問題について検討する。
われわれの限界は、プライバシー予算によって2つのプライバシー体制が存在することを示唆している。
我々はトップ2アルゴリズムの$epsilon$-global DP変種であるAdaP-TTを提案する。
論文 参考訳（メタデータ） (2023-09-05T13:07:25Z) - Theoretically Principled Federated Learning for Balancing Privacy and
Utility [61.03993520243198]
モデルパラメータを歪ませることでプライバシを保護する保護機構の一般学習フレームワークを提案する。
フェデレートされた学習における各コミュニケーションラウンドにおいて、各クライアント上の各モデルパラメータに対して、パーソナライズされたユーティリティプライバシトレードオフを実現することができる。
論文 参考訳（メタデータ） (2023-05-24T13:44:02Z) - Connect the Dots: Tighter Discrete Approximations of Privacy Loss
Distributions [49.726408540784334]
PLDベースの会計の鍵となる問題は、特定の個別サポートに対してPLDと(潜在的に連続的な)PLDをどのように近似するかである。
悲観的推定はすべての悲観的推定の中で最良であることを示す。
論文 参考訳（メタデータ） (2022-07-10T04:25:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。