| Register
\(\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.