Michał Dereziński

Email: derezin at umich edu

I am an Assistant Professor of Computer Science and Engineering at the University of Michigan.

Previously, I was a postdoctoral fellow in the Department of Statistics at the University of California, Berkeley, and a research fellow at the Simons Institute for the Theory of Computing (Fall 2018, Foundations of Data Science program). I obtained my Ph.D. in Computer Science at the University of California, Santa Cruz, advised by professor Manfred Warmuth. My research is focused on developing scalable randomized algorithms with robust statistical guarantees for machine learning, data science and optimization. Prior to UCSC, I completed Master's degrees in mathematics and computer science at the University of Warsaw. I also interned at a variety of Silicon Valley research labs (e.g. Microsoft, Yahoo, eBay), working on projects ranging from online learning to large-scale distributed optimization.

Research interests: Machine learning theory and algorithms, high-dimensional statistics, continuous and combinatorial optimization, randomized linear algebra, determinantal point processes, random matrix theory




Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs
M. Dereziński

Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches
M. Dereziński

Unbiased estimators for random design regression
M. Dereziński, M. K. Warmuth, D. Hsu
Journal of Machine Learning Research (to appear)  arXiv

Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence
S. Na, M. Dereziński, M. W. Mahoney

Domain Sparsification of Discrete Distributions using Entropic Independence
N. Anari, M. Dereziński, T.-D. Vuong, E. Yang
ITCS 2022  arXiv


Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
M. Dereziński, J. Lacotte, M. Pilanci, M. W. Mahoney
NeurIPS 2021 (spotlight presentation)  arXiv

Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence
X. Chen, M. Dereziński
COLT 2021  arXiv

Sparse sketches with small inversion bias
M. Dereziński, Z. Liao, E. Dobriban, M. W. Mahoney
COLT 2021  arXiv

LocalNewton: Reducing Communication Bottleneck for Distributed Learning
V. Gupta, A. Ghosh, M. Dereziński, R. Khanna, K. Ramchandran, M. W. Mahoney
UAI 2021  arXiv

Determinantal Point Processes in Randomized Numerical Linear Algebra
M. Dereziński, M. W. Mahoney
Notices of the AMS 68(1)  arXiv


Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization
M. Dereziński, B. Bartan, M. Pilanci, M. W. Mahoney
NeurIPS 2020  arXiv

Sampling from a k-DPP without looking at all items
D. Calandriello, M. Dereziński, M. Valko
NeurIPS 2020 (spotlight presentation)  arXiv

Precise expressions for random projections: Low-rank approximation and randomized Newton
M. Dereziński, F. Liang, Z. Liao, M. W. Mahoney
NeurIPS 2020  arXiv

Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nyström method
M. Dereziński, R. Khanna, M. W. Mahoney
NeurIPS 2020 (Best Paper Award)  arXiv

Exact expressions for double descent and implicit regularization via surrogate random design
M. Dereziński, F. Liang, M. W. Mahoney
NeurIPS 2020  arXiv

Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases
N. Anari, M. Dereziński
FOCS 2020  arXiv

Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling
M. Mutný, M. Dereziński, A. Krause
AISTATS 2020  arXiv

Bayesian experimental design using regularized determinantal point processes
M. Dereziński, F. Liang, M. W. Mahoney
AISTATS 2020  arXiv


Exact sampling of determinantal point processes with sublinear time preprocessing
M. Dereziński, D. Calandriello, M. Valko
NeurIPS 2019  arXiv

Distributed estimation of the inverse Hessian by determinantal averaging
M. Dereziński, M. W. Mahoney
NeurIPS 2019  arXiv

Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression
M. Dereziński, K. L. Clarkson, M. W. Mahoney, M. K. Warmuth
COLT 2019  arXiv

Fast determinantal point processes via distortion-free intermediate sampling
M. Dereziński
COLT 2019  arXiv

Correcting the bias in least squares regression with volume-rescaled sampling
M. Dereziński, M. K. Warmuth, D. Hsu
AISTATS 2019  arXiv


Leveraged volume sampling for linear regression
M. Dereziński, M. K. Warmuth, D. Hsu
NeurIPS 2018  arXiv

Reverse iterative volume sampling for linear regression
M. Dereziński, M. K. Warmuth
Journal of Machine Learning Research  arXiv

Subsampling for Ridge Regression via Regularized Volume Sampling
M. Dereziński, M. K. Warmuth
AISTATS 2018  arXiv  Poster  Talk

Batch-Expansion Training: An Efficient Optimization Framework
M. Dereziński, D. Mahajan, S. S. Keerthi, S.V.N. Vishwanathan, M. Weimer
AISTATS 2018  arXiv  Poster  Talk

Discovering Surprising Documents with Context-Aware Word Representations
M. Dereziński, K. Rohanimanesh, A. Hydrie
IUI 2018  PDF  Talk

2017 and older

Unbiased estimates for linear regression via volume sampling
M. Dereziński, M. K. Warmuth
NIPS 2017  arXiv  Poster  Spotlight

Anticipating Concept Drift in Online Learning
M. Dereziński, B. N. Bhaskar
LFED Workshop at NIPS 2015  PDF

The limits of squared Euclidean distance regularization
M. Dereziński, M. K. Warmuth
NIPS 2014  PDF  Spotlight

Active Semi-Supervised Concept Hierarchy Refinement
M. Dereziński
LAWS 2012 workshop  PDF