Polynomial time algorithms for dual volume sampling
We study dual volume sampling, a method for selecting k columns from an n ⇥ m short and wide matrix (n  k  m) such that the probability of selection is proportional to the volume spanned by the rows of the induced submatrix. This method was proposed by Avron and Boutsidis (2013), who showed it to be a promising method for column subset selection and its multiple applications. However, its wider adoption has been hampered by the lack of polynomial time sampling algorithms. We remove this hindrance by developing an exact (randomized) polynomial time sampling algorithm as well as its derandomization. Thereafter, we study dual volume sampling via the theory of real stable polynomials and prove that its distribution satisfies the "Strong Rayleigh" property. This result has numerous consequences, including a provably fast-mixing Markov chain sampler that makes dual volume sampling much more attractive to practitioners. This sampler is closely related to classical algorithms for popular experimental design methods that are to date lacking theoretical analysis but are known to empirically work well.
The paper studies efficient algorithms for sampling from a
determinantal distribution that the authors call "dual volume
sampling", for selecting a subset of columns from a matrix.
The main results in the paper are two sampling algorithms for
selecting k columns from an n x m matrix (n<=k<=m):
- an exact sampling procedure with time complexity O(k m^4)
- an approximate sampling, with time complexity O(k^3 n^2 m) (ignoring
log terms). 
The approximate sampling algorithm makes use of Strongly Rayleigh
measures, a technique previously used for approximately sampling from
closely related determinantal distributions, like Determinantal Point
Processes. Compared to the exact sampling, it offers a better
dependence on m, at the cost of the accuracy of sampling,
and a worse dependence on k and n. The authors perform some
preliminary experiments comparing their method to other 
subset selection techniques for linear regression. It is worth noting
that the plots are not very informative in comparing dual volume
sampling to leverage score sampling which is to my mind the most
relevant baseline.  
This determinantal distribution was previously discussed and motivated
in [1], who referred to it just as "volume sampling", and suggested
potential applications in linear regression, experimental design,
clustering, etc., however without providing a polynomial time
algorithm, except for the case of k=n.
The paper addresses an important topic that is relevant to
the NIPS community. The results are interesting, however the
contribution is somewhat limited. To my knowledge, the algorithms (in
particular, the exact sampling algorithm) are much slower compared
to Leverage Score sampling, and the authors did not make a compelling
argument for why DVS is better suited for the task of experimental
design. 
[1] Avron and Boutsidis. Faster Subset Selection For Matrices and
Applications, 2013. https://arxiv.org/abs/1201.0127