論文の概要: The planted matching problem: Sharp threshold and infinite-order phase
transition
- arxiv url: http://arxiv.org/abs/2103.09383v1
- Date: Wed, 17 Mar 2021 00:59:33 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-18 12:49:37.846348
- Title: The planted matching problem: Sharp threshold and infinite-order phase
transition
- Title（参考訳）: 植込みマッチング問題:シャープしきい値と無限次相転移
- Authors: Jian Ding, Yihong Wu, Jiaming Xu, Dana Yang
- Abstract要約: ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
- 参考スコア（独自算出の注目度）: 25.41713098167692
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of reconstructing a perfect matching $M^*$ hidden in a
randomly weighted $n\times n$ bipartite graph. The edge set includes every node
pair in $M^*$ and each of the $n(n-1)$ node pairs not in $M^*$ independently
with probability $d/n$. The weight of each edge $e$ is independently drawn from
the distribution $\mathcal{P}$ if $e \in M^*$ and from $\mathcal{Q}$ if $e
\notin M^*$. We show that if $\sqrt{d} B(\mathcal{P},\mathcal{Q}) \le 1$, where
$B(\mathcal{P},\mathcal{Q})$ stands for the Bhattacharyya coefficient, the
reconstruction error (average fraction of misclassified edges) of the maximum
likelihood estimator of $M^*$ converges to $0$ as $n\to \infty$. Conversely, if
$\sqrt{d} B(\mathcal{P},\mathcal{Q}) \ge 1+\epsilon$ for an arbitrarily small
constant $\epsilon>0$, the reconstruction error for any estimator is shown to
be bounded away from $0$ under both the sparse and dense model, resolving the
conjecture in [Moharrami et al. 2019, Semerjian et al. 2020]. Furthermore, in
the special case of complete exponentially weighted graph with $d=n$,
$\mathcal{P}=\exp(\lambda)$, and $\mathcal{Q}=\exp(1/n)$, for which the sharp
threshold simplifies to $\lambda=4$, we prove that when $\lambda \le
4-\epsilon$, the optimal reconstruction error is $\exp\left( -
\Theta(1/\sqrt{\epsilon}) \right)$, confirming the conjectured infinite-order
phase transition in [Semerjian et al. 2020].
- Abstract（参考訳）: ランダムに重み付けされた$n\times n$ bipartite graph に隠された完全マッチング $M^*$ の再構成問題について検討する。
エッジ集合は、$M^*$の全てのノード対と、$n(n-1)$のノード対は、確率$d/n$と独立に$M^*$のノード対を含む。
各辺$e$の重みは、分布 $\mathcal{P}$ if $e \in M^*$ と $\mathcal{Q}$ if $e \notin M^*$ から独立に引き出される。
もし$\sqrt{d} b(\mathcal{p},\mathcal{q}) \le 1$, where $b(\mathcal{p},\mathcal{q})$ が bhattacharyya 係数を表すなら、$m^*$ の最大許容推定値の再構成誤差(平均的偏差)は$0$ で$n\to \infty$となる。
逆に、$\sqrt{d} B(\mathcal{P},\mathcal{Q}) \ge 1+\epsilon$ for a arbitrarily small constant $\epsilon>0$ とすると、任意の推定器の再構成誤差はスパースモデルと密度モデルの両方の下で0$から外され、 [Moharrami et al] の予想が解かれる。
2019年、semerjian et al。
2020].
さらに、$d=n$, $\mathcal{p}=\exp(\lambda)$, and $\mathcal{q}=\exp(1/n)$という指数重み付き完全グラフの特別な場合において、鋭いしきい値が$\lambda=4$ に単純化される場合、$\lambda \le 4-\epsilon$ のとき、最適な再構成誤差は$\exp\left(\theta(1/\sqrt{\epsilon}) \right)$であり、[semerjian et al における無限次相転移の予想を確認する。
2020].
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - 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) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Fitting an ellipsoid to a quadratic number of random points [10.208117253395342]
問題 $(mathrmP)$ が $n$ の標準ガウス確率ベクトルを $mathbbRd$ で中心楕円体の境界に収まることを $n, d to infty$ とみなす。
任意の$varepsilon > 0$ に対して、$n leq (1 - varepsilon) d2 / 4$ ならば、$(mathrmP)$ は高い確率の解を持つ。
論文 参考訳（メタデータ） (2023-07-03T17:46:23Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Matrix concentration inequalities and efficiency of random universal
sets of quantum gates [0.0]
ランダム集合 $mathcalS の部分集合 U(d)$ に対して、$mathcalS$ が $delta$-approximate $t$-design となる確率の有界性を与える。
正確な$t$-designから引き出された$mathcalS$に対して、$delta$-approximate $t$-designが不等式$mathbbPleft(delta geq x right)leq 2D_tを満たす確率を示す。
論文 参考訳（メタデータ） (2022-02-10T23:44:09Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Sharper bounds for online learning of smooth functions of a single
variable [0.0]
ここでは$opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$を示します。
また、$opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$ も示します。
論文 参考訳（メタデータ） (2021-05-30T23:06:21Z) - Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。
疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
論文 参考訳（メタデータ） (2020-06-17T09:21: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。