論文の概要: Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2405.18534v1
- Date: Tue, 28 May 2024 19:02:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-30 22:03:07.100819
- Title: Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization
- Title（参考訳）: 組合せ最適化におけるサブサンプリングによる個別プライバシ会計
- Authors: Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Adam Sealfon,
- Abstract要約: 本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。
我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
- 参考スコア（独自算出の注目度）: 55.81991984375959
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we give a new technique for analyzing individualized privacy accounting via the following simple observation: if an algorithm is one-sided add-DP, then its subsampled variant satisfies two-sided DP. From this, we obtain several improved algorithms for private combinatorial optimization problems, including decomposable submodular maximization and set cover. Our error guarantees are asymptotically tight and our algorithm satisfies pure-DP while previously known algorithms (Gupta et al., 2010; Chaturvedi et al., 2021) are approximate-DP. We also show an application of our technique beyond combinatorial optimization by giving a pure-DP algorithm for the shifting heavy hitter problem in a stream; previously, only an approximateDP algorithm was known (Kaplan et al., 2021; Cohen & Lyu, 2023).
- Abstract（参考訳）: 本研究では,アルゴリズムが一方のAdd-DPである場合,そのサブサンプル版が両側のDPを満たすという単純な観察を通して,個別化されたプライバシ会計を解析する新しい手法を提案する。
これにより、分解可能な部分モジュラ最大化や集合被覆を含む、プライベート組合せ最適化問題に対する改良されたアルゴリズムがいくつか得られる。
我々の誤差保証は漸近的に厳密であり、我々のアルゴリズムは純粋DPを満足する一方、既知アルゴリズム(Gupta et al , 2010; Chaturvedi et al , 2021)は近似DPである。
また,ストリーム内の重み付け問題に純粋DPアルゴリズムを付与することにより,組合せ最適化を超越した手法を適用した(Kaplan et al ,2021; Cohen & Lyu, 2023)。
関連論文リスト
- Differentially Private Optimization with Sparse Gradients [60.853074897282625]
微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。
これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-04-16T20:01:10Z) - Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
本稿では,条件付き選好ネットワーク(CP-nets)上での選好を集約する近似アルゴリズムの設計と解析について述べる。
その焦点は、一般に最適な解が指数関数的な大きさであることが知られている、いわゆる「エンフスワップ」よりも、優先的な選好を集約することである。
論文 参考訳（メタデータ） (2023-12-14T17:31:38Z) - User-level Differentially Private Stochastic Convex Optimization:
Efficient Algorithms with Optimal Rates [16.958088684785668]
我々は,実行時において凸関数と強凸関数の両方に対して最適なレートを求める,ユーザレベルのDP-SCOの新しいアルゴリズムを開発した。
我々のアルゴリズムは、時間内に非滑らかな関数に対して最適な速度を得る最初の方法である。
論文 参考訳（メタデータ） (2023-11-07T08:26:51Z) - On Private Online Convex Optimization: Optimal Algorithms in
$\ell_p$-Geometry and High Dimensional Contextual Bandits [9.798304879986604]
本研究では,分散分布からサンプリングしたストリーミングデータを用いてDPの凸最適化問題について検討し,逐次到着する。
また、プライベート情報に関連するパラメータを更新し、新しいデータ(しばしばオンラインアルゴリズム)に基づいてリリースする連続リリースモデルについても検討する。
提案アルゴリズムは,1pleq 2$のときの最適余剰リスクと,2pleqinfty$のときの非プライベートな場合の最先端の余剰リスクを線形時間で達成する。
論文 参考訳（メタデータ） (2022-06-16T12:09:47Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - No-Regret Algorithms for Private Gaussian Process Bandit Optimization [13.660643701487002]
プライバシー保護統計のレンズによるガウス過程(GP)帯域最適化の至るところでの問題点を考察する。
均一なカーネル近似器とランダムな摂動を組み合わせた差分プライベートGPバンディット最適化のためのソリューションを提案する。
我々のアルゴリズムは最適化手順を通して微分プライバシを保持し、予測のためのサンプルパスに明示的に依存しない。
論文 参考訳（メタデータ） (2021-02-24T18:52:24Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。