論文の概要: Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation

• arxiv url: http://arxiv.org/abs/2306.04924v1
• Date: Thu, 8 Jun 2023 04:00:00 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-09 16:24:00.819844
• Title: Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation
• Title（参考訳）: 分散平均推定におけるコミュニケーション・生産性・ユーティリティトレードオフの厳密な最適性
• Authors: Berivan Isik, Wei-Ning Chen, Ayfer Ozgur, Tsachy Weissman, Albert No
• Abstract要約: 通信における平均推定問題と局所的差分プライバシー制約について検討する。 我々は,共用ランダム性の存在下でのEmphexact-Optimalアプローチを特徴付けるための一歩を踏み出した。
• 参考スコア（独自算出の注目度）: 14.890198588904381
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the mean estimation problem under communication and local differential privacy constraints. While previous work has proposed \emph{order}-optimal algorithms for the same problem (i.e., asymptotically optimal as we spend more bits), \emph{exact} optimality (in the non-asymptotic setting) still has not been achieved. In this work, we take a step towards characterizing the \emph{exact}-optimal approach in the presence of shared randomness (a random variable shared between the server and the user) and identify several necessary conditions for \emph{exact} optimality. We prove that one of the necessary conditions is to utilize a rotationally symmetric shared random codebook. Based on this, we propose a randomization mechanism where the codebook is a randomly rotated simplex -- satisfying the necessary properties of the \emph{exact}-optimal codebook. The proposed mechanism is based on a $k$-closest encoding which we prove to be \emph{exact}-optimal for the randomly rotated simplex codebook.
• Abstract（参考訳）: 通信における平均推定問題と局所的差分プライバシー制約について検討する。 前回の研究では、同じ問題(つまり、より多くのビットを費やすときに漸近的に最適)に対する \emph{order}-optimalアルゴリズムを提案したが、(非漸近的な設定において) \emph{exact} の最適性はまだ達成されていない。 本研究では,共有ランダム性(サーバとユーザの間で共有される確率変数)の存在下での \emph{exact}-optimal アプローチを特徴付け, \emph{exact} 最適性に必要ないくつかの条件を同定する。 必要条件の1つは、回転対称な共有ランダムコードブックを利用することである。 そこで本研究では,コードブックがランダムに回転する単純集合であるランダム化機構を提案する。 提案手法は,ランダムに回転する単純なコードブックに対して,emph{exact}-optimalであることが証明された$k$-closestエンコーディングに基づいている。

関連論文リスト

• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。 また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
  論文  参考訳（メタデータ） (2022-05-05T06:43:46Z)
• Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization [28.862321453597918]
  非滑らかな有限サム最小化は機械学習の基本的な問題である。 本稿では,確率的リシャフリングを用いた分散近位勾配アルゴリズムを開発し,その問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-11-06T07:29:55Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。 本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
  論文  参考訳（メタデータ） (2021-06-22T15:50:45Z)
• Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
  本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。 この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。 滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
  論文  参考訳（メタデータ） (2020-10-22T22:54:54Z)
• On the Optimality of Randomization in Experimental Design: How to Randomize for Minimax Variance and Design-Based Inference [58.442274475425144]
  条件平均値が与えられたセットで異なる場合の2本腕制御実験のミニマックス最適設計について検討する。 最適設計はカラスの混合戦略最適設計(MSOD)であることが示されている。 そこで,このような制約を受けるすべての設計において,最小値が最適である推論制約MSODを提案する。
  論文  参考訳（メタデータ） (2020-05-06T21:43:50Z)

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

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