15 citations · 57 across the 14 of their papers we have counts for
15 papers
Escaping Saddle Points with Compressed SGD
Dmitrii Avdiukhin, Grigory Yaroslavtsev
Stochastic gradient descent (SGD) is a prevalent optimization technique for large-scale distributed machine learning. While SGD computation can be efficiently divided between multi…
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto +4
Hierarchical Clustering is an unsupervised data analysis method which has been widely used for decades. Despite its popularity, it had an underdeveloped analytical foundation and t…
Fast Fourier Sparsity Testing
Grigory Yaroslavtsev, Samson Zhou
A function is -sparse if it has at most non-zero Fourier coefficients. Motivated by applications to fast sparse Fourier transforms over $…
"Bring Your Own Greedy"+Max: Near-Optimal -Approximations for Submodular Knapsack
Dmitrii Avdiukhin, Grigory Yaroslavtsev, Samson Zhou
The problem of selecting a small-size representative summary of a large dataset is a cornerstone of machine learning, optimization and data science. Motivated by applications to re…
Approximate -Sketching of Valuation Functions
Grigory Yaroslavtsev, Samson Zhou
We study the problem of constructing a linear sketch of minimum dimension that allows approximation of a given real-valued function …
Adversarially Robust Submodular Maximization under Knapsack Constraints
Dmitrii Avdiukhin, Slobodan Mitrović, Grigory Yaroslavtsev +1
We propose the first adversarially robust algorithm for monotone submodular maximization under single and multiple knapsack constraints with scalable implementations in distributed…