論文の概要: Private graphon estimation via sum-of-squares
- arxiv url: http://arxiv.org/abs/2403.12213v2
- Date: Thu, 18 Apr 2024 17:35:16 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-19 20:20:09.205551
- Title: Private graphon estimation via sum-of-squares
- Title（参考訳）: 2乗和によるプライベートグラフオン推定
- Authors: Hongjie Chen, Jingqiu Ding, Tommaso d'Orsi, Yiding Hua, Chih-Hung Liu, David Steurer,
- Abstract要約: ブロックモデルを学習し,任意のブロックに対して一定の実行時間でグラフトン推定を行うための,最初の純粋ノード微分プライベートアルゴリズムを開発した。
統計的ユーティリティは、これらの問題に対する以前の最良の情報理論(指数時間)ノードプライドメカニズムのそれと一致することを保証している。
- 参考スコア（独自算出の注目度）: 10.00024942014117
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We develop the first pure node-differentially-private algorithms for learning stochastic block models and for graphon estimation with polynomial running time for any constant number of blocks. The statistical utility guarantees match those of the previous best information-theoretic (exponential-time) node-private mechanisms for these problems. The algorithm is based on an exponential mechanism for a score function defined in terms of a sum-of-squares relaxation whose level depends on the number of blocks. The key ingredients of our results are (1) a characterization of the distance between the block graphons in terms of a quadratic optimization over the polytope of doubly stochastic matrices, (2) a general sum-of-squares convergence result for polynomial optimization over arbitrary polytopes, and (3) a general approach to perform Lipschitz extensions of score functions as part of the sum-of-squares algorithmic paradigm.
- Abstract（参考訳）: 確率ブロックモデルを学習し,任意のブロック数の多項式ランニング時間を用いたグラフトン推定のための,最初の純ノード微分プライベートアルゴリズムを開発した。
統計的効用は、これらの問題に対する以前の最良の情報理論(指数時間)ノードプライド機構のそれと一致することを保証している。
このアルゴリズムは、ブロック数に依存する2乗緩和の和で定義されるスコア関数の指数的なメカニズムに基づいている。
結果の主な要素は,(1)2つの確率行列のポリトープ上の2次最適化によるブロックグラモン間距離の特徴づけ,(2)任意のポリトープ上の多項式最適化のための2次収束結果の一般化,(3)総和2乗アルゴリズムパラダイムの一部としてスコア関数のリプシッツ拡張を実行するための一般アプローチである。
関連論文リスト
- Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust [5.037313459134419]
本稿では,ErdHos-R'enyiランダムグラフのエッジ密度を推定するアルゴリズムについて述べる。
我々は,アルゴリズムの誤り率を対数的因子まで最適とする情報理論的下界を証明した。
論文 参考訳（メタデータ） (2024-05-26T18:59:44Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Polynomial-Time Approximation of Zero-Free Partition Functions [9.153066211741356]
局所ハミルトニアンによって定義された古典的および量子的分割関数を推定するためのアルゴリズム時間アルゴリズムを提案する。
この結果はPaterとRegtsのアプローチを拡張し、一般化する新しい抽象的なフレームワークに基づいています。
論文 参考訳（メタデータ） (2022-01-30T09:54:45Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳（メタデータ） (2021-05-23T19:21:55Z) - A Bayesian Approach to Block-Term Tensor Decomposition Model Selection
and Computation [10.91885508254207]
いわゆるブロック項分解(BTD)テンソルモデル(特にランク=(L_r,L_r,1)$バージョン)は近年注目を集めている。
BTDモデル構造、すなわちブロック項の数とその個々のランクを推定するという課題は、最近になって注目され始めたばかりです。
ランク-$(L_r,L_r,1)$ BTDモデルの選択と計算の問題を、列の間隔を直交するアイデアに基づいて解くためのベイズ的アプローチが採られる。
論文 参考訳（メタデータ） (2021-01-08T09:37:21Z) - Constructing Segmented Differentiable Quadratics to Determine
Algorithmic Run Times and Model Non-Polynomial Functions [0.0]
アルゴリズム効率の連続的な進行を決定する手法を提案する。
提案手法は,任意のインデックスに対して,実行時の動作を$F$で効果的に決定できる。
論文 参考訳（メタデータ） (2020-12-03T00:22:49Z) - Slice Sampling for General Completely Random Measures [74.24975039689893]
本稿では, 後続推定のためのマルコフ連鎖モンテカルロアルゴリズムについて, 補助スライス変数を用いてトランケーションレベルを適応的に設定する。
提案アルゴリズムの有効性は、いくつかの一般的な非パラメトリックモデルで評価される。
論文 参考訳（メタデータ） (2020-06-24T17:53:53Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。