39 citations · 101 across the 17 of their papers we have counts for
8 papers · 1 filter
Robust Algorithms on Adaptive Inputs from Bounded Adversaries
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff +3
We study dynamic algorithms robust to adaptive input generated from sources with bounded capabilities, such as sparsity or limited interaction. For example, we consider robust line…
Optimal Query Complexities for Dynamic Trace Estimation
David P. Woodruff, Fred Zhang, Qiuyi Zhang
We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly…
Optimal Sketching for Trace Estimation
Shuli Jiang, Hai Pham, David P. Woodruff +2
Matrix trace estimation is ubiquitous in machine learning applications and has traditionally relied on Hutchinson's method, which requires matrix-vector product…
Span Recovery for Deep Neural Networks with Applications to Input Obfuscation
Rajesh Jayaram, David P. Woodruff, Qiuyi Zhang
The tremendous success of deep neural networks has motivated the need to better understand the fundamental properties of these networks, but many of the theoretical results propose…
Regularized Weighted Low Rank Approximation
Frank Ban, David Woodruff, Qiuyi Zhang
The classical low rank approximation problem is to find a rank matrix (where has columns and has rows) that minimizes the Frobenius norm of . Altho…
Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
Yin Tat Lee, Zhao Song, Qiuyi Zhang
Many convex problems in machine learning and computer science share the same form: \begin{align*} \min_{x} \sum_{i} f_i( A_i x + b_i), \end{align*} where are convex functions…
Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels
Arun Ganesh, Qiuyi Zhang
We consider the phylogenetic tree reconstruction problem with insertions and deletions (indels). Phylogenetic algorithms proceed under a model where sequences evolve down the model…
Convergence Results for Neural Networks via Electrodynamics
Rina Panigrahy, Sushant Sachdeva, Qiuyi Zhang
We study whether a depth two neural network can learn another depth two network using gradient descent. Assuming a linear output node, we show that the question of whether gradient…