42 citations · 247 across the 29 of their papers we have counts for
7 papers · 1 filter
Sparse sketches with small inversion bias
Michał Dereziński, Zhenyu Liao, Edgar Dobriban +1
For a tall matrix and a random sketching matrix , the sketched estimate of the inverse covariance matrix is typically biased: $E[(\…
Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization
Michał Dereziński, Burak Bartan, Mert Pilanci +1
In distributed second order optimization, a standard strategy is to average many local estimates, each of which is based on a small sketch or batch of the data. However, the local…
Sampling from a -DPP without looking at all items
Daniele Calandriello, Michał Dereziński, Michal Valko
Determinantal point processes (DPPs) are a useful probabilistic model for selecting a small diverse subset out of a large collection of items, with applications in summarization, s…
Precise expressions for random projections: Low-rank approximation and randomized Newton
Michał Dereziński, Feynman Liang, Zhenyu Liao +1
It is often desirable to reduce the dimensionality of a large dataset by projecting it onto a low-dimensional subspace. Matrix sketching has emerged as a powerful technique for per…
Determinantal Point Processes in Randomized Numerical Linear Algebra
Michał Dereziński, Michael W. Mahoney
Randomized Numerical Linear Algebra (RandNLA) uses randomness to develop improved algorithms for matrix problems that arise in scientific computing, data science, machine learning,…
Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases
Nima Anari, Michał Dereziński
We define a notion of isotropy for discrete set distributions. If is a distribution over subsets of a ground set , we say that is in isotropic position if $P[e \in…
Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nyström method
Michał Dereziński, Rajiv Khanna, Michael W. Mahoney
The Column Subset Selection Problem (CSSP) and the Nyström method are among the leading tools for constructing small low-rank approximations of large datasets in machine learning a…