論文の概要: Distributed Optimization with Feasible Set Privacy

• arxiv url: http://arxiv.org/abs/2312.02112v1
• Date: Mon, 4 Dec 2023 18:45:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-18 13:15:34.991247
• Title: Distributed Optimization with Feasible Set Privacy
• Title（参考訳）: 実現可能な集合プライバシーによる分散最適化
• Authors: Shreya Meel, Sennur Ulukus,
• Abstract要約: 2つのエージェントは、実行可能なセットを$mathcalP1$と$mathcalP1$を互いにプライベートに保ちながら、最適なソリューションセットを学ぶ。 エージェントの1つが$mathcalP$をプライベートにチェックする、シーケンシャルなプライベート情報検索(SPIR)フレームワークを採用しています。 SPIR-based private set intersection (PSI) プロトコルで実現可能な$mathcalP1$をプライベートに取得するのに対し、最適な方法を見つけるには、情報漏洩が少なく、ダウンロードも少ないため、我々の手法の方が優れていることを示す。
• 参考スコア（独自算出の注目度）: 35.16231062731263
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the setup of a constrained optimization problem with two agents $E_1$ and $E_2$ who jointly wish to learn the optimal solution set while keeping their feasible sets $\mathcal{P}_1$ and $\mathcal{P}_2$ private from each other. The objective function $f$ is globally known and each feasible set is a collection of points from a global alphabet. We adopt a sequential symmetric private information retrieval (SPIR) framework where one of the agents (say $E_1$) privately checks in $\mathcal{P}_2$, the presence of candidate solutions of the problem constrained to $\mathcal{P}_1$ only, while learning no further information on $\mathcal{P}_2$ than the solution alone. Further, we extract an information theoretically private threshold PSI (ThPSI) protocol from our scheme and characterize its download cost. We show that, compared to privately acquiring the feasible set $\mathcal{P}_1\cap \mathcal{P}_2$ using an SPIR-based private set intersection (PSI) protocol, and finding the optimum, our scheme is better as it incurs less information leakage and less download cost than the former. Over all possible uniform mappings of $f$ to a fixed range of values, our scheme outperforms the former with a high probability.
• Abstract（参考訳）: 制約付き最適化問題を2つのエージェント$E_1$と$E_2$で設定し、それらの実現可能な集合$\mathcal{P}_1$と$\mathcal{P}_2$を互いにプライベートに保ちながら最適な解集合を学習したいと考える。 目的関数 $f$ はグローバルに知られており、各実現可能な集合はグローバルアルファベットからの点の集合である。 エージェントの1つ(例えば$E_1$)が$\mathcal{P}_2$、$\mathcal{P}_1$のみに制限された問題の候補解の存在をプライベートにチェックし、$\mathcal{P}_2$についてそれ以上の情報を学習しないシーケンシャル対称プライベート情報検索(SPIR)フレームワークを採用する。 さらに,提案手法から理論的にプライベートなしきい値PSI(ThPSI)プロトコルを抽出し,そのダウンロードコストを特徴付ける。 提案手法は,SPIRプロトコルを用いて実現可能な集合である$\mathcal{P}_1\cap \mathcal{P}_2$をプライベートに取得するよりも,情報漏洩が少なく,ダウンロードコストも低いため,最適であることを示す。 固定範囲の値に対して$f$の可能な全ての一様写像において、我々のスキームは、高い確率で前者より優れる。

関連論文リスト

• Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs [35.22742439337603]
  Proposed Primal-Dual based Regularized Accelerated Natural Policy Gradient (PDR-ANPG) algorithm using entropy and quadratic regularizers to reach this goal。 PDR-ANPGは、パラメータ化されたポリシークラスに変換互換性の近似誤差を持たせるため、最終値の$epsilon$Optimity gapを達成できる。 これは、汎用パラメータ化CMDPの最先端最終保証の大幅な改善である。
  論文  参考訳（メタデータ） (2024-08-21T10:44:57Z)
• Optimal Bound for PCA with Outliers using Higher-Degree Voronoi Diagrams [0.0]
  本稿では,主成分分析 (PCA) のための新しいアルゴリズムについて紹介する。 外れ値が存在する場合でも、PCAの最適部分空間にナビゲートする。 このアプローチは、$nd+mathcalO(1)textpoly(n,d)$の時間複雑性を持つ最適解を得る。
  論文  参考訳（メタデータ） (2024-08-13T13:05:36Z)
• Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems [7.5573375809946395]
  我々は、ピアツーピア通信により、$m$のコンピューティングエージェントのネットワークが協調すると考えている。 我々のアルゴリズムフレームワークは、二変数のコンセンサス制約を取り除くために、アグラジアン乗算器を導入している。 我々の知る限りでは、これはNCSCミニマックス問題に対する収束保証を、原始変数と双対変数の両方に適用する一般の非正規化器で提供する最初の研究である。
  論文  参考訳（メタデータ） (2023-07-14T01:32:16Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Single-Server Private Linear Transformation: The Joint Privacy Case [10.072633952908456]
  本稿では,プライベート情報検索とプライベート線形計算の問題を一般化するPLT(Private Linear Transformation)の問題を紹介する。 この問題には、1つ以上のリモートサーバが$K$メッセージを格納する(IDコピー)ことと、$D$サブセットの独立線形結合を$L$で計算したいユーザが含まれている。
  論文  参考訳（メタデータ） (2021-06-09T17:09:22Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。