AIConfPaper
← Search

Michal Derezinski

18 accepted papers

2025

Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project

Pratik Rathore, Zachary Frangella, Sachin Garg, Shaghayegh Fazliani, Michal Derezinski, Madeleine Udell
NeurIPS 2025poster

Gaussian processes (GPs) play an essential role in biostatistics, scientific machine learning, and Bayesian optimization for their ability to provide probabilistic predictions and model uncertainty. However, GP inference struggles to scale to large datasets (which are common in modern applications),…

Cited by 0Source ↗code ↗Scholar ↗
2024

Distributed Least Squares in Small Space via Sketching and Bias Reduction

Sachin Garg, Kevin Tan, Michal Derezinski
NeurIPS 2024poster

Matrix sketching is a powerful tool for reducing the size of large data matrices. Yet there are fundamental limitations to this size reduction when we want to recover an accurate estimator for a task such as least square regression. We show that these limitations can be circumvented in the distribut…

Cited by 2Source ↗PDF ↗Scholar ↗
2021

Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update

Michal Derezinski, Jonathan Lacotte, Mert Pilanci, Michael W. Mahoney
NeurIPS 2021spotlight

In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. Randomized sketching has emerged as a powerful technique for constructing estimates of the Hessian which can be used to perform approximate Newton steps. This involv…

Cited by 37Source ↗PDF ↗code ↗Scholar ↗
2020

Bayesian experimental design using regularized determinantal point processes

Michal Derezinski, Feynman Liang, Michael Mahoney
AISTATS 2020poster

We establish a fundamental connection between Bayesian experimental design and determinantal point processes (DPPs). Experimental design is a classical task in combinatorial optimization, where we wish to select a small subset of $d$-dimensional vectors to minimize a statistical optimality criterion…

Cited by 27Source ↗PDF ↗Scholar ↗
2020

Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization

Michal Derezinski, Burak Bartan, Mert Pilanci, Michael W. Mahoney
NeurIPS 2020poster

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 estimates on each machine are typically biased, relative to the full solution on all of the data, and this can limit th…

Cited by 34Source ↗PDF ↗Scholar ↗
2020

Exact expressions for double descent and implicit regularization via surrogate random design

Michal Derezinski, Feynman T Liang, Michael W. Mahoney
NeurIPS 2020poster

Double descent refers to the phase transition that is exhibited by the generalization error of unregularized learning models when varying the ratio between the number of parameters and the number of training samples. The recent success of highly over-parameterized machine learning models such as dee…

Cited by 89Source ↗PDF ↗Scholar ↗
2020

Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystrom method

Michal Derezinski, Rajiv Khanna, Michael W. Mahoney
NeurIPS 2020oral

The Column Subset Selection Problem (CSSP) and the Nystrom method are among the leading tools for constructing small low-rank approximations of large datasets in machine learning and scientific computing. A fundamental question in this area is: how well can a data subset of size k compete with the b…

Cited by 54Source ↗PDF ↗code ↗Scholar ↗
2020

Precise expressions for random projections: Low-rank approximation and randomized Newton

Michal Derezinski, Feynman T Liang, Zhenyu Liao, Michael W. Mahoney
NeurIPS 2020poster

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 performing such dimensionality reduction very efficiently. Even though there is an extensive literature on the worst-case…

Cited by 35Source ↗PDF ↗Scholar ↗
2020

Sampling from a k-DPP without looking at all items

Daniele Calandriello, Michal Derezinski, Michal Valko
NeurIPS 2020spotlight

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, recommendation, stochastic optimization, experimental design and more. Given a kernel function and a subset size k, our g…

Cited by 34Source ↗PDF ↗code ↗Scholar ↗
2019

Correcting the bias in least squares regression with volume-rescaled sampling

Michal Derezinski, Manfred K. Warmuth, Daniel Hsu
AISTATS 2019poster

Consider linear regression where the examples are generated by an unknown distribution on R^d x R. Without any assumptions on the noise, the linear least squares solution for any i.i.d. sample will typically be biased w.r.t. the least squares optimum over the entire distribution. However, we show th…

Cited by 18Source ↗PDF ↗Scholar ↗
2018

Batch-Expansion Training: An Efficient Optimization Framework

Michal Derezinski, Dhruv Mahajan, S. Sathiya Keerthi, S. V. N. Vishwanathan, Markus Weimer
AISTATS 2018poster

We propose Batch-Expansion Training (BET), a framework for running a batch optimizer on a gradually expanding dataset. As opposed to stochastic approaches, batches do not need to be resampled i.i.d. at every iteration, thus making BET more resource efficient in a distributed setting, and when disk-a…

Cited by 0Source ↗PDF ↗Scholar ↗