124 citations · 276 across the 23 of their papers we have counts for
5 papers · 1 filter
Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
Anshumali Shrivastava, Zhao Song, Zhaozhuo Xu
We present the first provable Least-Squares Value Iteration (LSVI) algorithms that have runtime complexity sublinear in the number of actions. We formulate the value function estim…
Sketching Transformed Matrices with Applications to Natural Language Processing
Yingyu Liang, Zhao Song, Mengdi Wang +2
Suppose we are given a large matrix that cannot be stored in memory but is in a disk or is presented in a data stream. However, we need to compute a matrix decomposit…
Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
Sitan Chen, Jerry Li, Zhao Song
We consider the problem of learning a mixture of linear regressions (MLRs). An MLR is specified by nonnegative mixing weights summing to , and unknown…
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…
Nearly Optimal Dynamic -Means Clustering for High-Dimensional Data
Wei Hu, Zhao Song, Lin F. Yang +1
We consider the -means clustering problem in the dynamic streaming setting, where points from a discrete Euclidean space can be dynamically inserted to o…