4 papers
Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
Sandeep Silwal, David P. Woodruff, Qiuyi Zhang
We study beyond worst-case dimensionality reduction for -sparse vectors. Our work is divided into two parts, each focusing on a different facet of beyond worst-case analysis: We…
Adaptive Regret for Bandits Made Possible: Two Queries Suffice
Zhou Lu, Qiuyi Zhang, Xinyi Chen +3
Fast changing states or volatile environments pose a significant challenge to online optimization, which needs to perform rapid adaptation under limited observation. In this paper,…
Computing Approximate Sensitivities
Swati Padmanabhan, David P. Woodruff, Qiuyi Zhang
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, offerin…
Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products
Tamas Sarlos, Xingyou Song, David Woodruff +2
Inspired by fast algorithms in natural language processing, we study low rank approximation in the entrywise transformed setting where we want to find a good rank approximation…