2 citations · 7 across the 18 of their papers we have counts for
19 papers
John Ellipsoids via Lazy Updates
David P. Woodruff, Taisuke Yasuda
We give a faster algorithm for computing an approximate John ellipsoid around points in dimensions. The best known prior algorithms are based on repeatedly computing the le…
Ridge Leverage Score Sampling for Subspace Approximation
David P. Woodruff, Taisuke Yasuda
The subspace approximation problem is an NP-hard low rank approximation problem that generalizes the median hyperplane (), principal component analysis (), a…
Coresets for Multiple Regression
David P. Woodruff, Taisuke Yasuda
A coreset of a dataset with examples and features is a weighted subset of examples that is sufficient for solving downstream data analytic tasks. Nearly optimal constructio…
Reweighted Solutions for Weighted Low Rank Approximation
David P. Woodruff, Taisuke Yasuda
Weighted low rank approximation (WLRA) is an important yet computationally challenging primitive with applications ranging from statistical analysis, model compression, and signal…
SequentialAttention++ for Block Sparsification: Differentiable Pruning Meets Combinatorial Optimization
Taisuke Yasuda, Kyriakos Axiotis, Gang Fu +2
Neural network pruning is a key technique towards engineering large yet scalable, interpretable, and generalizable models. Prior work on the subject has developed largely along two…
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming
Gregory Dexter, Petros Drineas, David P. Woodruff +1
Sketching algorithms have recently proven to be a powerful approach both for designing low-space streaming algorithms as well as fast polynomial time approximation schemes (PTAS).…
Performance of Regularization for Sparse Convex Optimization
Kyriakos Axiotis, Taisuke Yasuda
Despite widespread adoption in practice, guarantees for the LASSO and Group LASSO are strikingly lacking in settings beyond statistical problems, and these algorithms are usually c…
Sharper Bounds for Sensitivity Sampling
David P. Woodruff, Taisuke Yasuda
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 in…
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online
David P. Woodruff, Taisuke Yasuda
Subset selection for the rank approximation of an matrix offers improvements in the interpretability of matrices, as well as a variety of computational savings.…
Sequential Attention for Feature Selection
Taisuke Yasuda, MohammadHossein Bateni, Lin Chen +3
Feature selection is the problem of selecting a subset of features for a machine learning model that maximizes model quality subject to a budget constraint. For neural networks, pr…
Online Lewis Weight Sampling
David P. Woodruff, Taisuke Yasuda
The seminal work of Cohen and Peng introduced Lewis weight sampling to the theoretical computer science community, yielding fast row sampling algorithms for approximating -dimen…
High-Dimensional Geometric Streaming in Polynomial Space
David P. Woodruff, Taisuke Yasuda
Many existing algorithms for streaming geometric data analysis have been plagued by exponential dependencies in the space complexity, which are undesirable for processing high-dime…
Active Linear Regression for Norms and Beyond
Cameron Musco, Christopher Musco, David P. Woodruff +1
We study active sampling algorithms for linear regression, which aim to query only a few entries of a target vector and output a near minimizer to $\min_{x\in\mat…
Improved Algorithms for Low Rank Approximation from Sparsity
David P. Woodruff, Taisuke Yasuda
We overcome two major bottlenecks in the study of low rank approximation by assuming the low rank factors themselves are sparse. Specifically, (1) for low rank approximation with s…
Exponentially Improved Dimensionality Reduction for : Subspace Embeddings and Independence Testing
Yi Li, David P. Woodruff, Taisuke Yasuda
Despite many applications, dimensionality reduction in the -norm is much less understood than in the Euclidean norm. We give two new oblivious dimensionality reduction tech…
Graph Spanners in the Message-Passing Model
Manuel Fernandez, David P. Woodruff, Taisuke Yasuda
Graph spanners are sparse subgraphs which approximately preserve all pairwise shortest-path distances in an input graph. The notion of approximation can be additive, multiplicative…
The Query Complexity of Mastermind with Distances
Manuel Fernandez, David P. Woodruff, Taisuke Yasuda
Consider a variant of the Mastermind game in which queries are distances, rather than the usual Hamming distance. That is, a codemaker chooses a hidden vector $\mathbf{y}\…
Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel -means Clustering
Manuel Fernandez, David P. Woodruff, Taisuke Yasuda
We present tight lower bounds on the number of kernel evaluations required to approximately solve kernel ridge regression (KRR) and kernel -means clustering (KKMC) on input…
The nonlinear stability regime of the viscous Faraday wave problem
David Altizio, Ian Tice, Xinyu Wu +1
This paper concerns the dynamics of a layer of incompressible viscous fluid lying above a vertically oscillating rigid plane and with an upper boundary given by a free surface. We…