Fugu-MT 論文翻訳(概要): Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs

論文の概要: Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs

arxiv url: http://arxiv.org/abs/2409.16688v1
Date: Wed, 25 Sep 2024 07:23:58 GMT
ステータス: 処理完了
システム内更新日: 2024-09-27 05:00:58.118860
Title: Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs
Title（参考訳）: デジェネリアシー境界グラフの局所微分プライバシーに基づくサイクルカウント
Authors: Quentin Hillebrand, Vorapong Suppakitpaisarn, Tetsuo Shibuya,
Abstract要約: 我々のアルゴリズムは、縮退有界グラフに対する (O(n1.5 + sqrtC_4) = O(n2)) の予測誤差を達成する。アルゴリズムの中核となる考え方は、前処理ステップに続く正確な三角形の数である。
参考スコア（独自算出の注目度）: 2.9123921488295768
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We propose an algorithm for counting the number of cycles under local differential privacy for degeneracy-bounded input graphs. Numerous studies have focused on counting the number of triangles under the privacy notion, demonstrating that the expected $\ell_2$-error of these algorithms is $\Omega(n^{1.5})$, where $n$ is the number of nodes in the graph. When parameterized by the number of cycles of length four ($C_4$), the best existing triangle counting algorithm has an error of $O(n^{1.5} + \sqrt{C_4}) = O(n^2)$. In this paper, we introduce an algorithm with an expected $\ell_2$-error of $O(\delta^{1.5} n^{0.5} + \delta^{0.5} d_{\max}^{0.5} n^{0.5})$, where $\delta$ is the degeneracy and $d_{\max}$ is the maximum degree of the graph. For degeneracy-bounded graphs ($\delta \in \Theta(1)$) commonly found in practical social networks, our algorithm achieves an expected $\ell_2$-error of $O(d_{\max}^{0.5} n^{0.5}) = O(n)$. Our algorithm's core idea is a precise count of triangles following a preprocessing step that approximately sorts the degree of all nodes. This approach can be extended to approximate the number of cycles of length $k$, maintaining a similar $\ell_2$-error, namely $O(\delta^{(k-2)/2} d_{\max}^{0.5} n^{(k-2)/2} + \delta^{k/2} n^{(k-2)/2})$ or $O(d_{\max}^{0.5} n^{(k-2)/2}) = O(n^{(k-1)/2})$ for degeneracy-bounded graphs.
Abstract（参考訳）: そこで本稿では,デジェネリティーに縛られた入力グラフに対して,局所的な差分プライバシーの下でサイクル数をカウントするアルゴリズムを提案する。多くの研究は、プライバシーの概念の下で三角形の数を数えることに重点を置いており、これらのアルゴリズムの期待される $\ell_2$-エラーが $\Omega(n^{1.5})$ であることを証明している。長さ 4 のサイクル数 ($C_4$ によってパラメータ化されるとき、最良の三角法カウントアルゴリズムは $O(n^{1.5} + \sqrt{C_4}) = O(n^2)$ の誤差を持つ。本稿では, 予測値 $\delta^{1.5} n^{0.5} + \delta^{0.5} d_{\max}^{0.5} n^{0.5})$ を持つアルゴリズムを導入する。実用的なソーシャルネットワークで一般的に見られる縮退有界グラフ ($\delta \in \Theta(1)$ に対して、我々のアルゴリズムは、(O(d_{\max}^{0.5} n^{0.5}) = O(n)\) の予測された $\ell_2$-エラーを達成する。我々のアルゴリズムの中核的な考え方は、全てのノードの次数をほぼソートする前処理ステップに続く正確な三角形の数である。このアプローチは、同じ $\ell_2$-エラーである$O(\delta^{(k-2)/2} d_{\max}^{0.5} n^{(k-2)/2} + \delta^{k/2} n^{(k-2)/2})$または$O(d_{\max}^{0.5} n^{(k-2)/2}) = O(n^{(k-1)/2})$を維持するために拡張できる。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文参考訳（メタデータ） (2024-08-16T02:33:07Z)
Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文参考訳（メタデータ） (2024-06-07T08:26:31Z)
Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文参考訳（メタデータ） (2024-02-22T02:20:24Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization [20.54801745090522]
我々は、mathbbRd f(x) 三角形q mathbbE_xi [Fxi]$inf(x)$ Lipschitz における $min_x という形式の問題を考察する。最近提案された勾配なし法は、少なくとも$mathcalO(L4 d3/2 epsilon-4 + Goldstein L d3/2 delta-1 epsilon-4)$ 0次複雑性を必要とする。
論文参考訳（メタデータ） (2023-01-16T13:33:37Z)
Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文参考訳（メタデータ） (2022-04-13T22:18:47Z)
Coresets for Data Discretization and Sine Wave Fitting [39.18104905459739]
N]:=1,cdots,N$の整数列は、センサから受信される。目標は、これまでに受け取った$n$ポイントを1つの周波数で近似することである。経験的集合 $P$ of $n$ が加重部分集合 $Ssubseteq P$ を持つことを証明している。
論文参考訳（メタデータ） (2022-03-06T17:07:56Z)
Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
論文参考訳（メタデータ） (2021-11-02T05:26:10Z)
Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
論文参考訳（メタデータ） (2021-05-31T14:41:40Z)
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)

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

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