SGA: A Robust Algorithm for Partial Recovery of Tree-Structured\n Graphical Models with Noisy Samples

We consider learning Ising tree models when the observations from the nodes\nare corrupted by independent but non-identically distributed noise with unknown\nstatistics. Katiyar et al. (2020) showed that although the exact tree structure\ncannot be recovered, one can recover a partial tree structure; that is, a\nstructure belonging to the equivalence class containing the true tree. This\npaper presents a systematic improvement of Katiyar et al. (2020). First, we\npresent a novel impossibility result by deriving a bound on the necessary\nnumber of samples for partial recovery. Second, we derive a significantly\nimproved sample complexity result in which the dependence on the minimum\ncorrelation $\\rho_{\\min}$ is $\\rho_{\\min}^{-8}$ instead of $\\rho_{\\min}^{-24}$.\nFinally, we propose Symmetrized Geometric Averaging (SGA), a more statistically\nrobust algorithm for partial tree recovery. We provide error exponent analyses\nand extensive numerical results on a variety of trees to show that the sample\ncomplexity of SGA is significantly better than the algorithm of Katiyar et al.\n(2020). SGA can be readily extended to Gaussian models and is shown via\nnumerical experiments to be similarly superior.\n