Nicholas J. A. Harvey

activity

20062022

most citedTight Analyses for Non-Smooth Stochastic Gradient Descent

21 citations · 101 across the 20 of their papers we have counts for

collaborators

Showing 2017Show all

3 papers · 1 filter

math.CO2017★ 1 cited

Short proofs for generalizations of the Lovász Local Lemma: Shearer's condition and cluster expansion

Nicholas J. A. Harvey, Jan Vondrák

The Lovász Local Lemma is a seminal result in probabilistic combinatorics. It gives a sufficient condition on a probability space and a collection of events for the existence of an…

cs.LG2017★ 4 cited

Near-optimal Sample Complexity Bounds for Robust Learning of Gaussians Mixtures via Compression Schemes

Hassan Ashtiani, Shai Ben-David, Nick Harvey +3

We prove that $Θ ~ (k d^{2} / ε^{2})$ samples are necessary and sufficient for learning a mixture of $k$ Gaussians in $R^{d}$ , up to error $ε$ in total va…

cs.DM2017

Matroids Hitting Sets and Unsupervised Dependency Grammar Induction

Nicholas Harvey, Vahab Mirrokni, David Karger +2

This paper formulates a novel problem on graphs: find the minimal subset of edges in a fully connected graph, such that the resulting graph contains all spanning trees for a set of…