Pipage Rounding, Pessimistic Estimators and Matrix Concentration

Abstract:
Negative dependence is a useful property of random variables, and one 
that is often exploited in algorithms based on dependent random 
sampling. But it does not seem to always be enough. In particular, while 
concentration results are known for sums of negatively dependent  
scalar-valued random variables, as well as sums of independent 
matrix-valued random variables, they are not known for sums of 
negatively dependent matrices.

We show how this obstacle can be bypassed for pipage rounding, an 
important and popular dependent rounding technique. Using a method we 
call "concavity of pessimistic estimators", we show concentration of 
submodular functions and concentration of matrix sums under pipage 
rounding. To prove the latter result, we derive a new variant of Lieb's 
celebrated concavity theorem in matrix analysis.

One main application of these results is to "spectrally-thin trees", a 
spectral analogue of the thin trees that played a crucial role in the 
recent breakthrough on the asymmetric travelling salesman problem.

(Joint work with Nick Harvey)