Fugu-MT 論文翻訳(概要): A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions

論文の概要: A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions

arxiv url: http://arxiv.org/abs/2304.06787v2
Date: Wed, 19 Apr 2023 23:11:52 GMT
ステータス: 処理完了
システム内更新日: 2023-04-21 16:03:24.181402
Title: A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions
Title（参考訳）: 二元積分布に対する多項式時間、純粋微分プライベート推定器
Authors: Vikrant Singhal
Abstract要約: 総偏差距離で0,1d$以上の製品分布を正確に推定する最初の$varepsilon$-differentially private,Computerly efficient algorithmを示す。
参考スコア（独自算出の注目度）: 2.094022863940315
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present the first $\varepsilon$-differentially private, computationally efficient algorithm that estimates the means of product distributions over $\{0,1\}^d$ accurately in total-variation distance, whilst attaining the optimal sample complexity to within polylogarithmic factors. The prior work had either solved this problem efficiently and optimally under weaker notions of privacy, or had solved it optimally while having exponential running times.
Abstract（参考訳）: 我々は,全変数距離で正確に$\{0,1\}^d$ の積分布平均を推定する最初の$\varepsilon$-differentially private, computationally efficientアルゴリズムを提案する。以前の作業では、この問題をより弱いプライバシー概念の下で効率的かつ最適に解決するか、指数的な実行時間を持ちながら最適に解決していた。

関連論文リスト

Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time [8.419603619167813]
所望のテレビ距離内において,$d$次元空間にマージンを持つ高次元半空間を学習するためのガウス時間アルゴリズムを提案する。我々のアルゴリズムはラベルを必要とせず、隠れたハーフスペースのユニークな(そして効率的な)識別性を確立する。超ポリノミカルな既存のモーメントバウンド保証の代わりに、トータル変分(TV)距離に基づくポリタイム保証を提供することにより、この問題を改善する。
論文参考訳（メタデータ） (2023-11-02T17:51:10Z)
Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文参考訳（メタデータ） (2023-06-07T14:07:35Z)
Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文参考訳（メタデータ） (2023-01-30T15:46:39Z)
Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
論文参考訳（メタデータ） (2022-12-15T18:27:39Z)
Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文参考訳（メタデータ） (2022-05-05T06:43:46Z)
Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文参考訳（メタデータ） (2020-12-23T17:07:26Z)
Faster Differentially Private Samplers via R\'enyi Divergence Analysis of Discretized Langevin MCMC [35.050135428062795]
ランゲヴィン力学に基づくアルゴリズムは、統計距離のようなある程度の距離測度の下で、はるかに高速な代替手段を提供する。我々の手法は単純で汎用的で、アンダーダムドランゲヴィン力学に適用できる。
論文参考訳（メタデータ） (2020-10-27T22:52:45Z)
SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
論文参考訳（メタデータ） (2020-06-12T05:00:44Z)
Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文参考訳（メタデータ） (2020-05-10T19:52:03Z)

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