Timezone: »
Poster
SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples
Anshoo Tandon · Aldric Han · Vincent Tan
We consider learning Ising tree models when the observations from the nodes are corrupted by independent but non-identically distributed noise with unknown statistics. Katiyar et al. (2020) showed that although the exact tree structure cannot be recovered, one can recover a partial tree structure; that is, a structure belonging to the equivalence class containing the true tree. This paper presents a systematic improvement of Katiyar et al. (2020). First, we present a novel impossibility result by deriving a bound on the necessary number of samples for partial recovery. Second, we derive a significantly improved sample complexity result in which the dependence on the minimum correlation $\rho_{\min}$ is $\rho_{\min}^{-8}$ instead of $\rho_{\min}^{-24}$. Finally, we propose Symmetrized Geometric Averaging (SGA), a more statistically robust algorithm for partial tree recovery. We provide error exponent analyses and extensive numerical results on a variety of trees to show that the sample complexity of SGA is significantly better than the algorithm of Katiyar et al. (2020). SGA can be readily extended to Gaussian models and is shown via numerical experiments to be similarly superior.
Author Information
Anshoo Tandon (National University of Singapore)
Aldric Han (National University of Singapore)
Vincent Tan (National University of Singapore)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples »
Fri. Jul 23rd 01:25 -- 01:30 AM Room
More from the Same Authors
-
2021 Poster: CIFS: Improving Adversarial Robustness of CNNs via Channel-wise Importance-based Feature Selection »
Hanshu YAN · Jingfeng Zhang · Gang Niu · Jiashi Feng · Vincent Tan · Masashi Sugiyama -
2021 Spotlight: CIFS: Improving Adversarial Robustness of CNNs via Channel-wise Importance-based Feature Selection »
Hanshu YAN · Jingfeng Zhang · Gang Niu · Jiashi Feng · Vincent Tan · Masashi Sugiyama -
2021 Poster: Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions »
Zixin Zhong · Wang Chi Cheung · Vincent Tan -
2021 Spotlight: Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions »
Zixin Zhong · Wang Chi Cheung · Vincent Tan -
2020 Poster: Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting »
Zixin Zhong · Wang Chi Cheung · Vincent Tan -
2020 Poster: Thompson Sampling Algorithms for Mean-Variance Bandits »
Qiuyu Zhu · Vincent Tan