1 citations · 1 across the 14 of their papers we have counts for
16 papers
High Probability Streaming Lower Bounds for Estimation
William Swartworth, David P. Woodruff, Samson Zhou
Estimating the second frequency moment () of an underlying frequency vector is a fundamental problem in the streaming model. While recent work by Braverman and Zamir [STOC 202…
Perfect Sampling with Polylogarithmic Update Time
William Swartworth, David P. Woodruff, Samson Zhou
Perfect sampling in a stream was introduced by Jayaram and Woodruff (FOCS 2018) as a streaming primitive which, given turnstile updates to a vector $x \in \{-\text{poly}(n),…
Unbiased Insights: Optimal Streaming Algorithms for Sampling, the Forget Model, and Beyond
Honghao Lin, Hoai-An Nguyen, William Swartworth +1
We study sampling and frequency moment estimation in a single-pass insertion-only data stream. For , we present a nearly space-optimal approximate sa…
Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model
Shiyuan Feng, William Swartworth, David P. Woodruff
We consider the heavy-hitters and moment estimation problems in the sliding window model. For moment estimation with , we show that it is possible to give a…
Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
Raphael A. Meyer, William Swartworth, David P. Woodruff
We study the computational model where we can access a matrix only by computing matrix-vector products for vectors of the form $\mathrm{x} = \ma…
Tight Sampling Bounds for Eigenvalue Approximation
William Swartworth, David P. Woodruff
We consider the problem of estimating the spectrum of a symmetric bounded entry (not necessarily PSD) matrix via entrywise sampling. This problem was introduced by [Bhattacharjee,…
Fast Sampling Based Sketches for Tensors
William Swartworth, David P. Woodruff
We introduce a new approach for applying sampling-based sketches to two and three mode tensors. We illustrate our technique to construct sketches for the classical problems of $\el…
Improving the Bit Complexity of Communication for Distributed Convex Optimization
Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan +3
We consider the communication complexity of some fundamental convex optimization problems in the point-to-point (coordinator) and blackboard communication models. We strengthen kno…
Fast and Low-Memory Compressive Sensing Algorithms for Low Tucker-Rank Tensor Approximation from Streamed Measurements
Cullen Haselby, Mark A. Iwen, Deanna Needell +2
In this paper we consider the problem of recovering a low-rank Tucker approximation to a massive tensor based solely on structured random compressive measurements. Crucially, the p…
Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign?
Erin George, Michael Murray, William Swartworth +1
We study benign overfitting in two-layer ReLU networks trained using gradient descent and hinge loss on noisy data for binary classification. In particular, we consider linearly se…
Optimal Eigenvalue Approximation via Sketching
William Swartworth, David P. Woodruff
Given a symmetric matrix , we show from the simple sketch , where is a Gaussian matrix with rows, that there is a procedure for approximating all eigen…
Population-Based Hierarchical Non-negative Matrix Factorization for Survey Data
Xiaofu Ding, Xinyu Dong, Olivia McGough +6
Motivated by the problem of identifying potential hierarchical population structure on modern survey data containing a wide range of complex data types, we introduce population-bas…
SP2: A Second Order Stochastic Polyak Method
Shuang Li, William J. Swartworth, Martin Takáč +2
Recently the "SP" (Stochastic Polyak step size) method has emerged as a competitive adaptive method for setting the step sizes of SGD. SP can be interpreted as a method specialized…
Testing Positive Semidefiniteness Using Linear Measurements
Deanna Needell, William Swartworth, David P. Woodruff
We study the problem of testing whether a symmetric input matrix is symmetric positive semidefinite (PSD), or is -far from the PSD cone, meaning that $λ_{\min}(…
Selectable Set Randomized Kaczmarz
Yotam Yaniv, Jacob D. Moorman, William Swartworth +3
The Randomized Kaczmarz method (RK) is a stochastic iterative method for solving linear systems that has recently grown in popularity due to its speed and low memory requirement. S…
Quantile-based Iterative Methods for Corrupted Systems of Linear Equations
Jamie Haddock, Deanna Needell, Elizaveta Rebrova +1
Often in applications ranging from medical imaging and sensor networks to error correction and data science (and beyond), one needs to solve large-scale linear systems in which a f…