15 citations · 28 across the 5 of their papers we have counts for
6 papers
A simpler strong refutation of random -XOR
Kwangjun Ahn
Strong refutation of random CSPs is a fundamental question in theoretical computer science that has received particular attention due to the long-standing gap between the informati…
SGD with shuffling: optimal rates without component convexity and large epoch requirements
Kwangjun Ahn, Chulhee Yun, Suvrit Sra
We study without-replacement SGD for solving finite-sum optimization problems. Specifically, depending on how the indices of the finite-sum are shuffled, we consider the RandomShuf…
On Tight Convergence Rates of Without-replacement SGD
Kwangjun Ahn, Suvrit Sra
For solving finite-sum optimization problems, SGD without replacement sampling is empirically shown to outperform SGD. Denoting by the number of components in the cost and …
From Nesterov's Estimate Sequence to Riemannian Acceleration
Kwangjun Ahn, Suvrit Sra
We propose the first global accelerated gradient method for Riemannian manifolds. Toward establishing our result we revisit Nesterov's estimate sequence technique and develop an al…
Computing the maximum matching width is NP-hard
Kwangjun Ahn, Jisu Jeong
The maximum matching width is a graph width parameter that is defined on a branch-decomposition over the vertex set of a graph. In this short paper, we prove that the problem of co…
Community Recovery in Hypergraphs
Kwangjun Ahn, Kangwook Lee, Changho Suh
Community recovery is a central problem that arises in a wide variety of applications such as network clustering, motion segmentation, face clustering and protein complex detection…