11 citations · 38 across the 20 of their papers we have counts for
7 papers · 1 filter
Submodular Maximization under the Intersection of Matroid and Knapsack Constraints
Yu-Ran Gu, Chao Bian, Chao Qian
Submodular maximization arises in many applications, and has attracted a lot of research attentions from various areas such as artificial intelligence, finance and operations resea…
Faster Algorithms for Structured Linear and Kernel Support Vector Machines
Yuzhou Gu, Zhao Song, Lichen Zhang
Quadratic programming is a ubiquitous prototype in convex programming. Many machine learning problems can be formulated as quadratic programming, including the famous Support Vecto…
Fast Sampling of -Matchings and -Edge Covers
Zongchen Chen, Yuzhou Gu
For an integer , a -matching (resp. -edge cover) of a graph is a subset of edges such that every vertex is incident with at most (resp. at l…
Optimal Bounds for Noisy Sorting
Yuzhou Gu, Yinzhan Xu
Sorting is a fundamental problem in computer science. In the classical setting, it is well-known that comparisons are both necessary and sufficient to sort…
Weak Recovery Threshold for the Hypergraph Stochastic Block Model
Yuzhou Gu, Yury Polyanskiy
We study the weak recovery problem on the -uniform hypergraph stochastic block model (-HSBM) with two balanced communities. In HSBM a random graph is constructed by placing h…
Uniqueness of BP fixed point for the Potts model and applications to community detection
Yuzhou Gu, Yury Polyanskiy
In the study of sparse stochastic block models (SBMs) one often needs to analyze a distributional recursion, known as the belief propagation (BP) recursion. Uniqueness of the fixed…
Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
Yuzhou Gu, Zhao Song, Junze Yin +1
Given a matrix , the low rank matrix completion problem asks us to find a rank- approximation of as for …