research
∙
08/30/2023
Surrogate-based Autotuning for Randomized Sketching Algorithms in Regression Problems
Algorithms from Randomized Numerical Linear Algebra (RandNLA) are known ...
share
research
∙
08/20/2022
Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
Sketch-and-project is a framework which unifies many known iterative met...
research
∙
06/21/2022
Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs
Algorithmic Gaussianization is a phenomenon that can arise when using ra...
research
∙
06/06/2022
Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches
Stochastic variance reduction has proven effective at accelerating first...
research
∙
04/20/2022
Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence
We consider minimizing a smooth and strongly convex objective function u...
research
∙
09/14/2021
Domain Sparsification of Discrete Distributions using Entropic Independence
We present a framework for speeding up the time it takes to sample from ...
research
∙
07/15/2021
Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
In second-order optimization, a potential bottleneck can be computing th...
research
∙
02/03/2021
Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence
Consider a regression problem where the learner is given a large collect...
research
∙
11/21/2020
Sparse sketches with small inversion bias
For a tall n× d matrix A and a random m× n sketching matrix S, the sketc...
research
∙
07/02/2020
Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization
In distributed second order optimization, a standard strategy is to aver...
research
∙
06/30/2020
Sampling from a k-DPP without looking at all items
Determinantal point processes (DPPs) are a useful probabilistic model fo...
research
∙
06/18/2020
Precise expressions for random projections: Low-rank approximation and randomized Newton
It is often desirable to reduce the dimensionality of a large dataset by...
research
∙
05/07/2020
Determinantal Point Processes in Randomized Numerical Linear Algebra
Randomized Numerical Linear Algebra (RandNLA) uses randomness to develop...
research
∙
04/20/2020
Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases
We define a notion of isotropy for discrete set distributions. If μ is a...
research
∙
02/21/2020
Improved guarantees and a multiple-descent curve for the Column Subset Selection Problem and the Nyström method
The Column Subset Selection Problem (CSSP) and the Nyström method are am...
research
∙
12/10/2019
Exact expressions for double descent and implicit regularization via surrogate random design
Double descent refers to the phase transition that is exhibited by the g...
research
∙
10/25/2019
Convergence Analysis of the Randomized Newton Method with Determinantal Sampling
We analyze the convergence rate of the Randomized Newton Method (RNM) in...
research
∙
07/08/2019
Unbiased estimators for random design regression
In linear regression we wish to estimate the optimum linear least square...
research
∙
06/10/2019
Bayesian experimental design using regularized determinantal point processes
In experimental design, we are given n vectors in d dimensions, and our ...
research
∙
05/31/2019
Exact sampling of determinantal point processes with sublinear time preprocessing
We study the complexity of sampling from a distribution over all index s...
research
∙
05/28/2019