論文の概要: Improved Lower Bound for Differentially Private Facility Location

• arxiv url: http://arxiv.org/abs/2403.04874v1
• Date: Thu, 7 Mar 2024 19:47:20 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-17 16:51:18.959753
• Title: Improved Lower Bound for Differentially Private Facility Location
• Title（参考訳）: 差動式私設施設における下界改善
• Authors: Pasin Manurangsi,
• Abstract要約: 我々は、Guptaらによって提案されたいわゆるスーパーセット出力設定における差分プライベート(DP)施設配置問題について考察する。 我々は、任意の$epsilon$-DPアルゴリズムの予測近似比に対して、$tildeOmegaleft(minleftlog n, sqrtfraclog nepsilonrightright)の低い境界を与える。
• 参考スコア（独自算出の注目度）: 37.39792744501348
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the differentially private (DP) facility location problem in the so called super-set output setting proposed by Gupta et al. [SODA 2010]. The current best known expected approximation ratio for an $\epsilon$-DP algorithm is $O\left(\frac{\log n}{\sqrt{\epsilon}}\right)$ due to Cohen-Addad et al. [AISTATS 2022] where $n$ denote the size of the metric space, meanwhile the best known lower bound is $\Omega(1/\sqrt{\epsilon})$ [NeurIPS 2019]. In this short note, we give a lower bound of $\tilde{\Omega}\left(\min\left\{\log n, \sqrt{\frac{\log n}{\epsilon}}\right\}\right)$ on the expected approximation ratio of any $\epsilon$-DP algorithm, which is the first evidence that the approximation ratio has to grow with the size of the metric space.
• Abstract（参考訳）: 我々はGuptaらによるいわゆるスーパーセット出力設定(SODA 2010)における差分プライベート(DP)施設配置問題について考察する。 現在最も知られている$\epsilon$-DPアルゴリズムの近似比は$O\left(\frac{\log n}{\sqrt{\epsilon}}\right)$である。 Cohen-Addad et al [AISTATS 2022] による。 本稿では、任意の$\epsilon$-DPアルゴリズムの予想近似比に対して、$\tilde{\Omega}\left(\min\left\{\log n, \sqrt{\frac{\log n}{\epsilon}}\right\right)$を与える。

関連論文リスト

• 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)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP [31.62899359543925]
  線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。 我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。 第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
  論文  参考訳（メタデータ） (2021-12-18T06:47:31Z)
• 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 Approximation Rate of ReLU Networks in terms of Width and Depth [5.37133760455631]
  本稿では,深部フィードフォワードニューラルネットワークの幅と深さの近似力に着目した。 幅$mathcalObig(maxdlfloor N1/drfloor,, N+2big)$と深さ$mathcalO(L)$のReLUネットワークは、近似レート$mathcalObig(lambdasqrtd (N2L2ln)で$[0,1]d$のH"古い連続関数を近似できる。
  論文  参考訳（メタデータ） (2021-02-28T13:15:55Z)
• 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)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。