| 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


      Add remark

      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


          Add remark

          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


              Add remark

              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


                  Add remark

                  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.