The Chernoff bound, being a sharp quantitative version of the law of large numbers, is incredibly useful in many contexts. Some general applications that come to mind (which I guess are really the same idea) are:
- bounding the sample complexity of PAC algorithms;
- estimating confidence intervals for polling (somewhat surprisingly, the Chernoff bound tells you that if you want to poll a population of $N$ people, the number $N$ doesn't really matter for the tradeoff between randomly sampled people and accuracy of the empirical average)
- more generally, very often in the analysis of randomized algorithms you need to argue that you have 'enough' samples, and Chernoff bounds are the way to go.
By now I feel like I have a good intuitive grasp of the power and limitations of Chernoff bounds. Basically, my question is about getting a similar understanding of matrix Chernoff bounds:
- How do I obtain a similar palette of 'classical' applications of matrix Chernoff bounds?
- What are some of the nice proofs they give us?
- Have they substantially simplified previous work that didn't explicitly use them?
I think matrix Chernoff bounds are still relatively new, so maybe there aren't really classical applications yet. But personally, I've used Tropp's monograph (https://arxiv.org/abs/1501.01571) and sections 5 and 6 of "Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications" (http://theoryofcomputing.org/articles/v004a003/) as references for applications.
Some examples of matrix Chernoff bounds simplifying previous work include the Alon-Roichman theorem (simplified here - http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r62) and results on Matrix Completion (simplified here - http://arxiv.org/abs/0910.0651).