論文の概要: How to Find a Point in the Convex Hull Privately
- arxiv url: http://arxiv.org/abs/2003.13192v1
- Date: Mon, 30 Mar 2020 02:42:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-18 08:49:04.483045
- Title: How to Find a Point in the Convex Hull Privately
- Title（参考訳）: 凸殻内の点をプライベートに見つける方法
- Authors: Haim Kaplan, Micha Sharir, Uri Stemmer
- Abstract要約: 入力集合の凸包における点を、微分プライベートな方法で$mathbb Rd$の$S$ of $n$pointでどのように計算するかという問題を研究する。
本稿では、$n=Omega(d4log X)$と仮定して、$O(nd)$時間で実行される微分プライベートアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 28.825332085193303
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the question of how to compute a point in the convex hull of an
input set $S$ of $n$ points in ${\mathbb R}^d$ in a differentially private
manner. This question, which is trivial non-privately, turns out to be quite
deep when imposing differential privacy. In particular, it is known that the
input points must reside on a fixed finite subset $G\subseteq{\mathbb R}^d$,
and furthermore, the size of $S$ must grow with the size of $G$. Previous works
focused on understanding how $n$ needs to grow with $|G|$, and showed that
$n=O\left(d^{2.5}\cdot8^{\log^*|G|}\right)$ suffices (so $n$ does not have to
grow significantly with $|G|$). However, the available constructions exhibit
running time at least $|G|^{d^2}$, where typically $|G|=X^d$ for some (large)
discretization parameter $X$, so the running time is in fact $\Omega(X^{d^3})$.
In this paper we give a differentially private algorithm that runs in
$O(n^d)$ time, assuming that $n=\Omega(d^4\log X)$. To get this result we study
and exploit some structural properties of the Tukey levels (the regions $D_{\ge
k}$ consisting of points whose Tukey depth is at least $k$, for $k=0,1,...$).
In particular, we derive lower bounds on their volumes for point sets $S$ in
general position, and develop a rather subtle mechanism for handling point sets
$S$ in degenerate position (where the deep Tukey regions have zero volume). A
naive approach to the construction of the Tukey regions requires $n^{O(d^2)}$
time. To reduce the cost to $O(n^d)$, we use an approximation scheme for
estimating the volumes of the Tukey regions (within their affine spans in case
of degeneracy), and for sampling a point from such a region, a scheme that is
based on the volume estimation framework of Lov\'asz and Vempala (FOCS 2003)
and of Cousins and Vempala (STOC 2015). Making this framework differentially
private raises a set of technical challenges that we address.
- Abstract（参考訳）: 入力集合の凸包内の点の計算方法に関する問題として,${\mathbb r}^d$ における$n$ の点を微分的にプライベートに計算する方法について検討する。
この質問は、自明でプライベートではないが、差分プライバシーを課すと、かなり深いことが判明した。
特に、入力点が固定有限部分集合 $G\subseteq{\mathbb R}^d$ に従わなければならないことが知られ、さらに、$S$ は$G$ の大きさで成長しなければならない。
以前の研究は、$n$が$|G|$でどのように成長する必要があるかを理解することに集中し、$n=O\left(d^{2.5}\cdot8^{\log^*|G|}\right)$ suffices(だから$n$は$|G|$で大きく成長する必要はない)を示した。
しかし、利用可能な構成では実行時間は少なくとも$|g|^{d^2}$であり、通常$|g|=x^d$は(大きな)離散化パラメータが$x$であるので、実行時間は$\omega(x^{d^3})$である。
本稿では,n=\Omega(d^4\log X)$と仮定して,O(n^d)$時間で動作する微分プライベートアルゴリズムを提案する。
この結果を得るために、我々はタキーレベルのいくつかの構造的性質を研究し、活用する(d_{\ge k}$ 領域は、タキー深さが少なくとも$k$、$k=0,1,...$)。
特に、点集合の体積上の下限を一般の位置に$s$として導出し、縮退位置(ディープ・タキー領域の体積がゼロである)の点集合を扱うための微妙なメカニズムを開発する。
タキー領域の構成には、$n^{O(d^2)}$時間を要する。
コストを$O(n^d)$に下げるために、タキー領域の体積を推定する近似スキーム(退化時にはアフィンスパンを含む)を使用し、そのような領域から点をサンプリングするために、Lov\'asz and Vempala (FOCS 2003) と Cousins and Vempala (STOC 2015) の体積推定フレームワークに基づくスキームを用いる。
このフレームワークを別々にプライベートにすることで、私たちが対処する技術的な課題が生まれます。
関連論文リスト
- Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry [20.068722738606287]
我々は、$(epsilon,delta)$-differential privacy(DP)の制約の下で、サドル点問題(SSP)と変分不等式(SVI)を研究する。
強いSPギャップ上の$tildeObig(frac1sqrtn + fracsqrtdnepsilonbig)$のバウンドを得る。
我々は、$の強いVI-ギャップ上の有界値を得る最初の解析を提供する。
論文 参考訳（メタデータ） (2024-11-07T21:45:05Z) - Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。
また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文 参考訳（メタデータ） (2023-05-12T08:43:28Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Faster Sampling from Log-Concave Distributions over Polytopes via a
Soft-Threshold Dikin Walk [28.431572772564518]
我々は、$d$-dimensional log-concave distribution $pi(theta) propto e-f(theta)$からポリトープ$K$に制約された$m$不等式をサンプリングする問題を考える。
我々の主な成果は、少なくとも$O((md + d L2 R2) times MDomega-1) log(fracwdelta)$ arithmetic operation to sample from $pi$ の "soft-warm' variant of the Dikin walk Markov chain" である。
論文 参考訳（メタデータ） (2022-06-19T11:33:07Z) - Sampling from Log-Concave Distributions with Infinity-Distance
Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。
また、ディキンウォークの「ソフトパイ」バージョンも提示する。
論文 参考訳（メタデータ） (2021-11-07T13:44:50Z) - 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) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Optimal Coreset for Gaussian Kernel Density Estimation [0.8376091455761259]
点集合 $Psubset mathbbRd$ が与えられたとき、$P$ の核密度推定は [ overlinemathcalG_P(x) = frac1left|Pright|sum_pin Pe-leftlVert x-p rightrVert2 ] for any $xinmathbbRd$ と定義される。
我々は、小さなサブセット$Q$ of $P を構築する方法を研究する。
論文 参考訳（メタデータ） (2020-07-15T22:58:50Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。