42 citations · 247 across the 29 of their papers we have counts for
18 papers · 1 filter
Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs
Michał Dereziński
Algorithmic Gaussianization is a phenomenon that can arise when using randomized sketching or sampling methods to produce smaller representations of large datasets: For certain tas…
Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence
Xue Chen, Michał Dereziński
Consider a regression problem where the learner is given a large collection of -dimensional data points, but can only query a small subset of the real-valued labels. How many qu…
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…
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…
Exact expressions for double descent and implicit regularization via surrogate random design
Michał Dereziński, Feynman Liang, Michael W. Mahoney
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…
Bayesian experimental design using regularized determinantal point processes
Michał Dereziński, Feynman Liang, Michael W. Mahoney
In experimental design, we are given vectors in dimensions, and our goal is to select of them to perform expensive measurements, e.g., to obtain labels/responses,…
Distributed estimation of the inverse Hessian by determinantal averaging
Michał Dereziński, Michael W. Mahoney
In distributed optimization and distributed numerical linear algebra, we often encounter an inversion bias: if we want to compute a quantity that depends on the inverse of a sum of…
Exact sampling of determinantal point processes with sublinear time preprocessing
Michał Dereziński, Daniele Calandriello, Michal Valko
We study the complexity of sampling from a distribution over all index subsets of the set with the probability of a subset proportional to the determinant of the…
Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression
Michał Dereziński, Kenneth L. Clarkson, Michael W. Mahoney +1
In experimental design, we are given a large collection of vectors, each with a hidden response value that we assume derives from an underlying linear model, and we wish to pick a…
Fast determinantal point processes via distortion-free intermediate sampling
Michał Dereziński
Given a fixed matrix , where , we study the complexity of sampling from a distribution over all subsets of rows where the probability of a subset is…
Correcting the bias in least squares regression with volume-rescaled sampling
Michał Dereziński, Manfred K. Warmuth, Daniel Hsu
Consider linear regression where the examples are generated by an unknown distribution on . Without any assumptions on the noise, the linear least squares solution for…
Reverse iterative volume sampling for linear regression
Michał Dereziński, Manfred K. Warmuth
We study the following basic machine learning task: Given a fixed set of -dimensional input points for a linear regression problem, we wish to predict a hidden response value fo…
Leveraged volume sampling for linear regression
Michał Dereziński, Manfred K. Warmuth, Daniel Hsu
Suppose an design matrix in a linear regression problem is given, but the response for each point is hidden unless explicitly requested. The goal is to sample only a s…
Subsampling for Ridge Regression via Regularized Volume Sampling
Michał Dereziński, Manfred K. Warmuth
Given vectors , we want to fit a linear regression model for noisy labels . The ridge estimator is a classical solution to this…
Unbiased estimates for linear regression via volume sampling
Michał Dereziński, Manfred K. Warmuth
Given a full rank matrix with more columns than rows, consider the task of estimating the pseudo inverse based on the pseudo inverse of a sampled subset of columns (of si…
Batch-Expansion Training: An Efficient Optimization Framework
Michał Dereziński, Dhruv Mahajan, S. Sathiya Keerthi +2
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 b…