
Michał Dereziński
Email: mderezin at berkeley edu I am a postdoc in the Department of Statistics at UC Berkeley, working with Michael Mahoney. Previously, I was 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 largescale distributed optimization. Research interests: Machine learning theory and algorithms, highdimensional statistics, continuous and combinatorial optimization, randomized linear algebra, determinantal point processes, random matrix theory
I'm currently on the job market, looking for faculty positions. 
Updates 

Education 
Ph.D. in Computer Science, University of California, Santa Cruz, 2018. 
Publications 
2021
Query Complexity of Least Absolute Deviation Regression
via Robust Uniform Convergence
Sparse sketches with small inversion bias
LocalNewton: Reducing Communication Bottleneck for Distributed Learning
Determinantal Point Processes
in Randomized Numerical Linear Algebra
Debiasing Distributed Second Order Optimization with Surrogate Sketching
and Scaled Regularization
Sampling from a kDPP without looking at all items
Precise expressions for random projections: Lowrank approximation and
randomized Newton
Improved guarantees and a multipledescent curve for
Column Subset Selection and the Nyström method
Exact expressions for double descent and implicit regularization via surrogate random design
Isotropy and LogConcave Polynomials: Accelerated Sampling and HighPrecision Counting of Matroid Bases
Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling
Bayesian experimental design using regularized determinantal point processes
Unbiased estimators for random design regression
Exact sampling of determinantal point processes with sublinear time preprocessing
Distributed estimation of the inverse Hessian by determinantal averaging
Minimax experimental design: Bridging the gap between statistical and worstcase approaches to least squares regression
Fast determinantal point processes via distortionfree intermediate sampling
Correcting the bias in least squares regression with volumerescaled sampling
Leveraged volume sampling for linear regression
Reverse iterative volume sampling for linear regression
Subsampling for Ridge Regression via Regularized Volume Sampling
BatchExpansion Training: An Efficient Optimization Framework
Discovering Surprising Documents with ContextAware Word Representations
Unbiased estimates for linear regression via volume sampling
Anticipating Concept Drift in Online Learning
The limits of squared Euclidean distance regularization
Active SemiSupervised Concept Hierarchy Refinement 
Internships 
Research Intern, Microsoft Research, Sunnyvale, CA
Intern Research Scientist, Yahoo Inc., Sunnyvale, CA
Intern Research Scientist, eBay Inc., San Jose, CA Software engineer Intern, Nvidia, Santa Clara, CA.
Intern, Interdisciplinary Centre for Mathematical and Computational Modelling, Warsaw, Poland. 