42 citations · 247 across the 29 of their papers we have counts for
32 papers
Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling
Xinchen Du, Elizaveta Rebrova, Michał Dereziński +1
We study an online sketched Newton method that approximates the Newton direction at each step via a state-of-the-art sketching solver, called the generalized accelerated sketch-and…
Debiasing Random Oblique Projections for Subsampled OLS and Fast CUR in High Dimensions
Chengmei Niu, Sachin Garg, Michał Dereziński +1
Random sampling is a fundamental tool in modern machine learning and numerical linear algebra for reducing the computational cost of large-scale matrix problems. Existing analyses,…
Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software
Riley Murray, James Demmel, Michael W. Mahoney +10
Randomized numerical linear algebra - RandNLA, for short - concerns the use of randomization as a resource to develop improved algorithms for large-scale linear algebra computation…
Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
Michał Dereziński, Elizaveta Rebrova
Sketch-and-project is a framework which unifies many known iterative methods for solving linear systems and their variants, as well as further extensions to non-linear optimization…
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…
Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches
Michał Dereziński
Stochastic variance reduction has proven effective at accelerating first-order algorithms for solving convex finite-sum optimization tasks such as empirical risk minimization. Inco…
Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence
Sen Na, Michał Dereziński, Michael W. Mahoney
We consider minimizing a smooth and strongly convex objective function using a stochastic Newton method. At each iteration, the algorithm is given an oracle access to a stochastic…
Domain Sparsification of Discrete Distributions using Entropic Independence
Nima Anari, Michał Dereziński, Thuy-Duong Vuong +1
We present a framework for speeding up the time it takes to sample from discrete distributions defined over subsets of size of a ground set of elements, in the regime $…
Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
Michał Dereziński, Jonathan Lacotte, Mert Pilanci +1
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 powerfu…
LocalNewton: Reducing Communication Bottleneck for Distributed Learning
Vipul Gupta, Avishek Ghosh, Michal Derezinski +3
To address the communication bottleneck problem in distributed optimization within a master-worker framework, we propose LocalNewton, a distributed second-order algorithm with loca…
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…
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…
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…
Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling
Mojmír Mutný, Michał Dereziński, Andreas Krause
We analyze the convergence rate of the randomized Newton-like method introduced by Qu et. al. (2016) for smooth and convex objectives, which uses random coordinate blocks of a Hess…
Unbiased estimators for random design regression
Michał Dereziński, Manfred K. Warmuth, Daniel Hsu
In linear regression we wish to estimate the optimum linear least squares predictor for a distribution over -dimensional input points and real-valued responses, based on a small…
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…