In large scale machine learning, random sampling is a popular way to approximate datasets
by a small representative subset of examples. In particular, sensitivity sampling is an …

The seminal work of Cohen and Peng [CP15](STOC 2015) introduced Lewis weight
sampling to the theoretical computer science community, which yields fast row sampling …

We advance both the theory and practice of robust $\ell_p $-quasinorm regression for $ p\in
(0, 1] $ by using novel variants of iteratively reweighted least-squares (IRLS) to solve the …

Many existing algorithms for streaming geometric data analysis have been plagued by
exponential dependencies in the space complexity, which are undesirable for processing …

We present an algorithm that given any n-vertex, m-edge, rank r hypergraph constructs a
spectral sparsifier with O (n ε− 2 log n log r) hyperedges in nearly-linear O (mr) time. This …

We consider the sparsification of sums F: ℝ n→ ℝ+ where F (x)= f 1 (⟨ a 1, x⟩)+⋯+ fm (⟨ am,
x⟩) for vectors a 1,…, am∈ ℝ n and functions f 1,…, fm: ℝ→ ℝ+. We show that (1+ ε) …

We study the performance of empirical risk minimization on the $ p $-norm linear regression
problem for $ p\in (1,\infty) $. We show that, in the realizable case, under no moment …

Recent works in dimensionality reduction for regression tasks have introduced the notion of
sensitivity, an estimate of the importance of a specific datapoint in a dataset, offering …

Recent works in dimensionality reduction for regression tasks have introduced the notion of
sensitivity, an estimate of the importance of a specific datapoint in a dataset, offering …

Given a matrix $\mathbf {A}\in\mathbb {R}^{k\times n} $, a partitioning of $[k] $ into groups $
S_1,\dots, S_m $, an outer norm $ p $, and a collection of inner norms such that either $ p\ge …