In this section, we provide a proof of thm:main in the case when \(X\)  is valued in \(\lbrace \pm 1\rbrace ^{m}/\sqrt{m}\)  almost surely. In the setting of sec:application, this corresponds to the case when the true data is Boolean and hence is particularly relevant for applications. Our proof relies on the so-called pinning lemma from statistical physics, discovered independently by Montanari [1]} and by Raghavendra and Tan [2]}. The statement below follows by combining [2]} with Pinsker's inequality (cf. the proofs of [4]}).
