research
∙
03/31/2023
Almost Linear Constant-Factor Sketching for ℓ_1 and Logistic Regression
We improve upon previous oblivious sketching and turnstile streaming res...
share
research
∙
07/14/2021
Oblivious sketching for logistic regression
What guarantees are possible for solving logistic regression in one pass...
research
∙
07/06/2021
Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020
Theoretical computer science (TCS) is a subdiscipline of computer scienc...
research
∙
04/27/2020
Input-Sparsity Low Rank Approximation in Schatten Norm
We give the first input-sparsity time algorithms for the rank-k low rank...
research
∙
11/16/2019
Regularized Weighted Low Rank Approximation
The classical low rank approximation problem is to find a rank k matrix ...
research
∙
09/03/2019
Oblivious Sketching of High-Degree Polynomial Kernels
Kernel methods are fundamental tools in machine learning that allow dete...
research
∙
06/11/2019
Faster Algorithms for High-Dimensional Robust Covariance Estimation
We study the problem of estimating the covariance matrix of a high-dimen...
research
∙
06/02/2019
Sample-Optimal Low-Rank Approximation of Distance Matrices
A distance matrix A ∈ R^n × m represents all pairwise distances, A_ij=d(...
research
∙
06/26/2018
Conditional Sparse ℓ_p-norm Regression With Optimal Probability
We consider the following conditional linear regression problem: the tas...
research
∙
03/06/2018