384 citations · 1.1k across the 22 of their papers we have counts for
6 papers · 1 filter
Nearly Linear Row Sampling Algorithm for Quantile Regression
Yi Li, Ruosong Wang, Lin Yang +1
We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data, improving upon the previous best algorithm w…
Efficient Symmetric Norm Regression via Linear Sketching
Zhao Song, Ruosong Wang, Lin F. Yang +2
We provide efficient algorithms for overconstrained linear regression problems with size when the loss function is a symmetric norm (a norm invariant under sign-flips…
The Communication Complexity of Optimization
Santosh S. Vempala, Ruosong Wang, David P. Woodruff
We consider the communication complexity of a number of distributed optimization problems. We start with the problem of solving a linear system. Suppose there is a coordinator toge…
Dimensionality Reduction for Tukey Regression
Kenneth L. Clarkson, Ruosong Wang, David P. Woodruff
We give the first dimensionality reduction methods for the overconstrained Tukey regression problem. The Tukey loss function has …
Tight Bounds for Oblivious Subspace Embeddings
Ruosong Wang, David P. Woodruff
An oblivious subspace embedding is a distribution over matrices such that for any fixed matrix , $$\Pr_Π[\textrm{for all }x, \ \|Ax\|_p \l…
An Improved Algorithm for Incremental DFS Tree in Undirected Graphs
Lijie Chen, Ran Duan, Ruosong Wang +2
Depth first search (DFS) tree is one of the most well-known data structures for designing efficient graph algorithms. Given an undirected graph with vertices and …