4
$\begingroup$

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?
$\endgroup$
1

2 Answers 2

4
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

To answer my question a bit, I've recently learned that Kyng and Sachdeva have used some matrix concentration inequalities to give a very simple Laplacian solver algorithm; paper here.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .