$\newcommand{\Cat}{{\rm Cat}}$ $\newcommand{\A}{\mathcal A}$ $\newcommand{\freestar}{ \framebox[7pt]{\star} }$

## 2. ML vs. Bayes

1. ### ML vs. Bayes for spiked tensors

#### Problem 2.1.

[Andrea Montanari] Let $x_0$ be a uniformly random unit vector and observe $Y = \lambda x_0^{\otimes d} + W$ where $W$ is a symmetric tensor with $W_{i_1,\ldots,i_d} \sim \mathcal{N}(0,1/n)$ independently (up to symmetry). Let $\lambda^\mathrm{Bayes}$ and $\lambda^\mathrm{ML}$ denote the thresholds at which Bayes-optimal inference and maximum-likelihood estimation (respectively) achieve non-trivial correlation with the truth $x_0$. It is conjectured that $\lambda^\mathrm{Bayes} = \lambda^\mathrm{ML}$. These thresholds are also conjectured to be equal for the case $d = 2$ when $x_0$ has entries sampled i.i.d. from $\mathrm{Unif}\{\pm 1/\sqrt{n}\}$.
• ### ML vs. Bayes for SBM

#### Problem 2.2.

[Allan Sly] In the SBM and related models, are there regimes in which maximum-likelihood reconstruction does not achieve the optimal threshold?
• ### Separation in trees and graphs

#### Problem 2.3.

There are many connections between the SBM and the broadcast model in trees (which describes local neighborhoods). Are there questions (e.g. threshold for ML) for which the answer is different on trees than on graphs?
• ### Suboptimality of SDP

#### Problem 2.4.

Are there regimes (even in the 2-block symmetric SBM) in which the SDP does not achieve the information-theoretic threshold?

Cite this as: AimPL: Connecting communities via the block model, available at http://aimpl.org/blockmodel.