論文の概要: Simple Binary Hypothesis Testing under Local Differential Privacy and
Communication Constraints
- arxiv url: http://arxiv.org/abs/2301.03566v2
- Date: Fri, 15 Dec 2023 22:48:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-19 21:19:19.261290
- Title: Simple Binary Hypothesis Testing under Local Differential Privacy and
Communication Constraints
- Title（参考訳）: 局所微分プライバシーと通信制約下での単純な二項仮説検証
- Authors: Ankit Pensia, Amir R. Asadi, Varun Jog, Po-Ling Loh
- Abstract要約: 局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。
我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
- 参考スコア（独自算出の注目度）: 8.261182037130407
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study simple binary hypothesis testing under both local differential
privacy (LDP) and communication constraints. We qualify our results as either
minimax optimal or instance optimal: the former hold for the set of
distribution pairs with prescribed Hellinger divergence and total variation
distance, whereas the latter hold for specific distribution pairs. For the
sample complexity of simple hypothesis testing under pure LDP constraints, we
establish instance-optimal bounds for distributions with binary support;
minimax-optimal bounds for general distributions; and (approximately)
instance-optimal, computationally efficient algorithms for general
distributions. When both privacy and communication constraints are present, we
develop instance-optimal, computationally efficient algorithms that achieve the
minimum possible sample complexity (up to universal constants). Our results on
instance-optimal algorithms hinge on identifying the extreme points of the
joint range set $\mathcal A$ of two distributions $p$ and $q$, defined as
$\mathcal A := \{(\mathbf T p, \mathbf T q) | \mathbf T \in \mathcal C\}$,
where $\mathcal C$ is the set of channels characterizing the constraints.
- Abstract（参考訳）: 我々は,ローカルディファレンシャルプライバシ(ldp)と通信制約の両方の下で,単純な二項仮説テストを行った。
前者は所定のヘリンジャー発散と全変動距離を持つ分布対の集合、後者は特定の分布対の集合の集合である。
純粋な LDP 制約下での単純な仮説テストのサンプル複雑性について、二元性を持つ分布のインスタンス最適境界、一般分布の最小最適境界、および(およそ)一般分布のインスタンス最適計算効率アルゴリズムを確立する。
プライバシと通信の制約がある場合、最小のサンプル複雑性(普遍定数まで)を達成するインスタンス最適化、計算効率のよいアルゴリズムを開発する。
共役範囲の極端点を識別するインスタンス最適化アルゴリズムのヒンジでは、$\mathcal A$ と $q$ を$\mathcal A := \{(\mathbf T p, \mathbf T q) | \mathbf T \in \mathcal C\}$ と定義し、$\mathcal C$ は制約を特徴づけるチャネルの集合である。
関連論文リスト
- Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳（メタデータ） (2023-08-17T21:15:04Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。
CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
論文 参考訳（メタデータ） (2022-06-13T15:58:14Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - The Minimax Complexity of Distributed Optimization [0.0]
分散最適化に適用可能な古典的なオラクルフレームワークの拡張である「グラフオラクルモデル」を紹介します。
私は「間欠的コミュニケーション設定」の具体例に焦点をあてる
コンベックス設定におけるSGD(Local Descent)アルゴリズムの理論的特性を解析する。
論文 参考訳（メタデータ） (2021-09-01T15:18:33Z) - Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
N$マシンは$sum_i = 1N f_i (x)$という関数の和を最小化することを目的としている。
我々の主な成果は、$N$マシンによって送信され受信される必要がある全ビット数に関する最初の完全に条件のない境界を提供する。
我々は、$Omega(Nd log d / Nvarepsilon)$ total bits をマシン間で通信し、$sum_i = 1N の最小値に対する加算 $epsilon$-approximation を見つける必要があることを示した。
論文 参考訳（メタデータ） (2020-10-16T08:10:02Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。