Finally, the proof of our main lower bound, presented in Section , relies on a combination of some delicate exact computations and multiple applications of the matrix Chernoff and Bernstein inequalities [1]}. Technical difficulties aside, the main challenge in proving our lower bound is constructing the example distribution used to establish that constrained least squares is suboptimal. In addition to the restrictions imposed by the boundedness constraints, we discuss other distributional assumptions sufficient to ensure that constrained least squares matches the rate (REF ) (see  Section REF ), thus making our main lower bound impossible. The intuition behind our construction is rooted in the form taken by our upper bounds. In particular, we construct a distribution tailored to make the localized multiplier process ill-behaved by simultaneously violating moment equivalence assumptions on the noise and statistical leverage score distributions. See Section  for more details.
