I just read this blog entry, and it is unclear to me why the tail bound results are not trivial for all bounded random matrices.

For instance, Corollary 4 states that for an $n\times n$ random matrix $M$ with i.i.d. mean-zero entries absolutely bounded by $1$, $P(\|M\|_{op} > A \sqrt{n}) \leq C \exp(-c A n)$ for all $A \geq C$, where $\|\|_{op}$ is the operator norm and $C, c > 0 $ are constants.

Since $\|M\|_{op}$ is bounded due to the boundedness of $M$'s entries, we can simply choose $C$ high enough so that $A \sqrt{n}$ necessarily surpasses this bound. The probability $P(\|M\|_{op} > A \sqrt{n})$ is then $0$, and the tail bound holds trivially for all choices of $c$.

Given there are no further qualifications on the $c$ and $C$, why is the result not trivial?

  • 2
    $\begingroup$ I didn't check the link, so this might be a stupid question. Are the constants are allowed to depend on $n$? If not, notice that $\| M \|_{op}$ is not bounded as $n$ varies, so this bound is nontrivial if it holds for infinitely many $n$ for the same values of the constants. $\endgroup$
    – Ian
    Aug 14, 2020 at 14:56
  • 1
    $\begingroup$ I don't really follow the conclusion that you can choose arbitrary positive constants $c$ and $C$, after all the bound is supposed to hold for all $A \geq C$. (So you don't have to freedom to choose $A$.) But I agree that choosing $C$ high enough such that $\mathbb{P}[||M|| > C\sqrt{n}] = 0$ seals the deal. I think that the power of such results comes from the specific constants involved. $\endgroup$ Aug 14, 2020 at 15:01
  • $\begingroup$ @infinite_monkey Yes, thanks for the correction; that was sloppy. $\endgroup$
    – bodhi
    Aug 14, 2020 at 15:04
  • 1
    $\begingroup$ @Ian I suspect you are right. The text seems vague as it says $c$ and $C$ are ``absolute constants''. I am not too familiar with math terminology, but this may indicate they cannot depend on $n$. $\endgroup$
    – bodhi
    Aug 14, 2020 at 15:28
  • 2
    $\begingroup$ Yes, absolute constants do not depend on $n$. The power of these sorts of concentration inequalities is that they hold for all $n$ (meaning the constant $C$ works for all $n$ too). To gain some intuition on concentration inequalities, I suggest working through the proof of Hoeffding's and/or Bernstein's inequality. $\endgroup$
    – brenderson
    Aug 14, 2020 at 15:50


You must log in to answer this question.