論文の概要: Single-Server Private Linear Transformation: The Joint Privacy Case
- arxiv url: http://arxiv.org/abs/2106.05220v1
- Date: Wed, 9 Jun 2021 17:09:22 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-10 14:50:44.754340
- Title: Single-Server Private Linear Transformation: The Joint Privacy Case
- Title(参考訳): 単一サーバのプライベートリニア変換: 共同プライバシケース
- Authors: Anoosheh Heidarzadeh, Nahid Esmati, and Alex Sprintson
- Abstract要約: 本稿では,プライベート情報検索とプライベート線形計算の問題を一般化するPLT(Private Linear Transformation)の問題を紹介する。
この問題には、1つ以上のリモートサーバが$K$メッセージを格納する(IDコピー)ことと、$D$サブセットの独立線形結合を$L$で計算したいユーザが含まれている。
- 参考スコア(独自算出の注目度): 10.072633952908456
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper introduces the problem of Private Linear Transformation (PLT)
which generalizes the problems of private information retrieval and private
linear computation. The PLT problem includes one or more remote server(s)
storing (identical copies of) $K$ messages and a user who wants to compute $L$
independent linear combinations of a $D$-subset of messages. The objective of
the user is to perform the computation by downloading minimum possible amount
of information from the server(s), while protecting the identities of the $D$
messages required for the computation. In this work, we focus on the
single-server setting of the PLT problem when the identities of the $D$
messages required for the computation must be protected jointly. We consider
two different models, depending on whether the coefficient matrix of the
required $L$ linear combinations generates a Maximum Distance Separable (MDS)
code. We prove that the capacity for both models is given by $L/(K-D+L)$, where
the capacity is defined as the supremum of all achievable download rates. Our
converse proofs are based on linear-algebraic and information-theoretic
arguments that establish connections between PLT schemes and linear codes. We
also present an achievability scheme for each of the models being considered.
- Abstract(参考訳): 本稿では,プライベート情報検索とプライベート線形計算の問題を一般化するPLT(Private Linear Transformation)の問題を紹介する。
PLTの問題には、1つ以上のリモートサーバが$K$メッセージを格納している(IDコピー)ことと、$D$サブセットの独立線形結合を$L$で計算したいユーザが含まれている。
ユーザの目的は、サーバから最小限の情報量をダウンロードし、計算に必要な$D$メッセージのIDを保護することで、計算を実行することである。
本研究では,計算に必要な$D$メッセージのIDを共同で保護しなければならない場合,PLT問題の単一サーバ設定に焦点を当てる。
必要となる$L$線形結合の係数行列が最大距離分離(MDS)符号を生成するかどうかによって、2つの異なるモデルを考える。
両方のモデルのキャパシティは$l/(k-d+l)$で与えられることが証明され、キャパシティはすべての実行可能ダウンロード率の上限として定義される。
逆証明は、線形代数的および情報理論的議論に基づいて、PLTスキームと線形符号の接続を確立する。
また、検討中の各モデルに対する達成可能性スキームも提示する。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳(メタデータ) (2024-03-08T18:50:19Z) - Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。
逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。
我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
論文 参考訳(メタデータ) (2023-11-02T03:41:58Z) - Corruption-Robust Offline Reinforcement Learning with General Function
Approximation [60.91257031278004]
一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。
我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
論文 参考訳(メタデータ) (2023-10-23T04:07:26Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳(メタデータ) (2022-04-11T17:26:19Z) - Settling the Communication Complexity for Distributed Offline
Reinforcement Learning [10.315054389907031]
オフライン強化学習(RL)において,複数の分散マシンが協調して問題解決を行う新たな環境について検討する。
各マシンが送信できる情報の総数(ビット数)には予算の制約がある。
文脈的包帯における値関数の予測と, エピソード的および非エピソード的MDPの双方に対して, ミニマックスリスクに対する情報理論的下限を確立する。
論文 参考訳(メタデータ) (2022-02-10T06:27:07Z) - Locally Differentially Private Reinforcement Learning for Linear Mixture
Markov Decision Processes [78.27542864367821]
強化学習(RL)アルゴリズムは、ユーザのプライベートで機密性の高いデータに依存するパーソナライズされたサービスを提供するために使用することができる。
ユーザのプライバシを保護するために、プライバシ保護RLアルゴリズムが要求されている。
線形混合MDPと呼ばれるマルコフ決定過程(MDP)のクラスを学習するための新しい$(varepsilon, delta)$-LDPアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-10-19T17:44:09Z) - Single-Server Private Linear Transformation: The Individual Privacy Case [10.072633952908456]
本稿では、個々のプライバシ保証を伴うシングルサーバのプライベートリニアトランスフォーメーション(PLT)問題について考察する。
目標は、計算に必要な各メッセージのアイデンティティを個別にプライベートに保ちながら、ダウンロードコストを最小限にすることである。
論文 参考訳(メタデータ) (2021-06-09T17:12:04Z) - Corella: A Private Multi Server Learning Approach based on Correlated
Queries [30.3330177204504]
データプライバシーを保護する代替手段として、$textitCorella$を提案する。
提案手法はサーバのクラスタに依存しており,少なくともmathbbN$のTは,それぞれが学習モデルを実行することでコロードを行うことができる。
ノイズのばらつきは、情報漏洩を最大$T$サーバの任意のサブセットに、理論的に無視できるほど大きく設定されている。
論文 参考訳(メタデータ) (2020-03-26T17:44:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。