論文の概要: Sampling from Log-Concave Distributions with Infinity-Distance
Guarantees and Applications to Differentially Private Optimization
- arxiv url: http://arxiv.org/abs/2111.04089v1
- Date: Sun, 7 Nov 2021 13:44:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-09 15:28:58.860770
- Title: Sampling from Log-Concave Distributions with Infinity-Distance
Guarantees and Applications to Differentially Private Optimization
- Title（参考訳）: 無限距離保証付きログコンケーブ分布からのサンプリングと微分プライベート最適化への応用
- Authors: Oren Mangoubi and Nisheeth K. Vishnoi
- Abstract要約: 本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。
また、ディキンウォークの「ソフトパイ」バージョンも提示する。
- 参考スコア（独自算出の注目度）: 33.38289436686841
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: For a $d$-dimensional log-concave distribution $\pi(\theta)\propto
e^{-f(\theta)}$ on a polytope $K$, we consider the problem of outputting
samples from a distribution $\nu$ which is $O(\varepsilon)$-close in
infinity-distance $\sup_{\theta\in K}|\log\frac{\nu(\theta)}{\pi(\theta)}|$ to
$\pi$. Such samplers with infinity-distance guarantees are specifically desired
for differentially private optimization as traditional sampling algorithms
which come with total-variation distance or KL divergence bounds are
insufficient to guarantee differential privacy. Our main result is an algorithm
that outputs a point from a distribution $O(\varepsilon)$-close to $\pi$ in
infinity-distance and requires
$O((md+dL^2R^2)\times(LR+d\log(\frac{Rd+LRd}{\varepsilon r}))\times
md^{\omega-1})$ arithmetic operations, where $f$ is $L$-Lipschitz, $K$ is
defined by $m$ inequalities, is contained in a ball of radius $R$ and contains
a ball of smaller radius $r$, and $\omega$ is the matrix-multiplication
constant. In particular this runtime is logarithmic in $\frac{1}{\varepsilon}$
and significantly improves on prior works. Technically, we depart from the
prior works that construct Markov chains on a
$\frac{1}{\varepsilon^2}$-discretization of $K$ to achieve a sample with
$O(\varepsilon)$ infinity-distance error, and present a method to convert
continuous samples from $K$ with total-variation bounds to samples with
infinity bounds. To achieve improved dependence on $d$, we present a
"soft-threshold" version of the Dikin walk which may be of independent
interest. Plugging our algorithm into the framework of the exponential
mechanism yields similar improvements in the running time of $\varepsilon$-pure
differentially private algorithms for optimization problems such as empirical
risk minimization of Lipschitz-convex functions and low-rank approximation,
while still achieving the tightest known utility bounds.
- Abstract（参考訳）: d$-次元ログ凹面分布 $\pi(\theta)\propto e^{-f(\theta)}$ on a polytope $K$ に対して、分布 $\nu$ that is $O(\varepsilon)$-close in infinity-distance $\sup_{\theta\in K}|\log\frac{\nu(\theta)}{\pi(\theta)}|$を$\pi$に出力する問題を考える。
差分プライバシーを保証するために、全差分距離やKL発散境界を持つ従来のサンプリングアルゴリズムが不十分であるため、無限距離保証を持つサンプルは、偏差プライベートな最適化のために特に望ましい。
我々の主な結果は、分布 $O(\varepsilon)$-close から $\pi$ infinity-distance に出力するアルゴリズムであり、$O((md+dL^2R^2)\times(LR+d\log(\frac{Rd+LRd}{\varepsilon r}))\times md^{\omega-1})$算術演算、$f$ is $L$-Lipschitz, $K$は$m$の不等式で定義される。
特に、このランタイムは$\frac{1}{\varepsilon}$で対数的であり、以前の処理を大幅に改善します。
技術的には、マルコフ連鎖を$\frac{1}{\varepsilon^2}$-離散化で構築し、$o(\varepsilon)$ infinity- distanceエラーのサンプルを達成する以前の研究から脱却し、全変数境界を持つ$k$から無限境界のサンプルへ連続的なサンプルを変換する方法を提案する。
$d$への依存を改善するために、独立した関心を持つかもしれないDikin walkの"ソフトスレッド"バージョンを提示する。
指数関数機構の枠組みにアルゴリズムを組み込むことで、リプシッツ凸関数の経験的リスク最小化や低ランク近似といった最適化問題に対する$\varepsilon$-pure微分的プライベートアルゴリズムの実行時間にも同様の改善が得られます。
関連論文リスト
- Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。
線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文 参考訳（メタデータ） (2024-09-05T16:59:56Z) - Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。
我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
論文 参考訳（メタデータ） (2024-06-10T17:48:36Z) - Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。
我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
論文 参考訳（メタデータ） (2024-05-25T08:34:49Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - 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) - 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) - On Robust Optimal Transport: Computational Complexity, Low-rank
Approximation, and Barycenter Computation [14.80695185915604]
我々は、最適なトランスポートの2つの頑健なバージョン、$textitRobust Semi-constrained Optimal Transport$ (RSOT) と $textitRobust Unconstrained Optimal Transport$ (ROT) を考える。
離散設定における両方の問題に対して、$widetildemathcalO(fracn2varepsilon)$timeでRSOTとROTの$varepsilon$-approximationsを生成するSinkhornベースのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-13T03:55:52Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。