12 citations · 39 across the 25 of their papers we have counts for
6 papers · 1 filter
Expected Size of Random Tukey Layers and Convex Layers
Zhengyang Guo, Yi Li, Shaoyu Pei
We study the Tukey layers and convex layers of a planar point set, which consists of points independently and uniformly sampled from a convex polygon with vertices. We show…
Streaming Complexity of SVMs
Alexandr Andoni, Collin Burns, Yi Li +2
We study the space complexity of solving the bias-regularized SVM problem in the streaming model. This is a classic supervised learning problem that has drawn lots of attention, in…
Learning the Positions in CountSketch
Simin Liu, Tianrui Liu, Ali Vakilian +2
We consider sketching algorithms which first quickly compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem…
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…
Input-Sparsity Low Rank Approximation in Schatten Norm
Yi Li, David Woodruff
We give the first input-sparsity time algorithms for the rank- low rank approximation problem in every Schatten norm. Specifically, for a given matrix , our algor…
Minimum Enclosing Parallelogram with Outliers
Zhengyang Guo, Yi Li
We study the problem of minimum enclosing rectangle with outliers, which asks to find, for a given set of planar points, a rectangle with minimum area that encloses at least $(…