21 citations · 94 across the 25 of their papers we have counts for
26 papers
Noise is All You Need: Private Second-Order Convergence of Noisy SGD
Dmitrii Avdiukhin, Michael Dinitz, Chenglin Fan +1
Private optimization is a topic of major interest in machine learning, with differentially private stochastic gradient descent (DP-SGD) playing a key role in both theory and practi…
Optimal Sample Complexity of Contrastive Learning
Noga Alon, Dmitrii Avdiukhin, Dor Elboim +2
Contrastive learning is a highly successful technique for learning representations of data from labeled tuples, specifying the distance relations within the tuple. We study the sam…
Tree Learning: Optimal Algorithms and Sample Complexity
Dmitrii Avdiukhin, Grigory Yaroslavtsev, Danny Vainstein +3
We study the problem of learning a hierarchical tree representation of data from labeled samples, taken from an arbitrary (and possibly adversarial) distribution. Consider a collec…
HOUDINI: Escaping from Moderately Constrained Saddles
Dmitrii Avdiukhin, Grigory Yaroslavtsev
We give the first polynomial time algorithms for escaping from high-dimensional saddle points under a moderate number of constraints. Given gradient access to a smooth function $f…
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…
Objective-Based Hierarchical Clustering of Deep Embedding Vectors
Stanislav Naumov, Grigory Yaroslavtsev, Dmitrii Avdiukhin
We initiate a comprehensive experimental study of objective-based hierarchical clustering methods on massive datasets consisting of deep embedding vectors from computer vision and…
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…
Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent
Dmitrii Avdiukhin, Sergey Pupyrev, Grigory Yaroslavtsev
Motivated by performance optimization of large-scale graph processing systems that distribute the graph across multiple machines, we consider the balanced graph partitioning proble…
Hierarchical Clustering for Euclidean Data
Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh +1
Recent works on Hierarchical Clustering (HC), a well-studied problem in exploratory data analysis, have focused on optimizing various objective functions for this problem under arb…
Optimality of Linear Sketching under Modular Updates
Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev
We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in dimensions, the existence of ef…
Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under -Distances
Grigory Yaroslavtsev, Adithya Vadapalli
We present massively parallel (MPC) algorithms and hardness of approximation results for computing Single-Linkage Clustering of input -dimensional vectors under Hamming, $\e…
Linear Sketching over
Sampath Kannan, Elchanan Mossel, Grigory Yaroslavtsev
We initiate a systematic study of linear sketching over . For a given Boolean function a randomized -sketch is a distribu…
Privacy for the Protected (Only)
Michael Kearns, Aaron Roth, Zhiwei Steven Wu +1
Motivated by tensions between data privacy for individual citizens, and societal priorities such as counterterrorism and the containment of infectious disease, we introduce a compu…
Tight Bounds for Linear Sketches of Approximate Matchings
Sepehr Assadi, Sanjeev Khanna, Yang Li +1
We resolve the space complexity of linear sketches for approximating the maximum matching problem in dynamic graph streams where the stream may include both edge insertion and dele…
Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs
Shuchi Chawla, Konstantin Makarychev, Tselil Schramm +1
We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality g…
Going for Speed: Sublinear Algorithms for Dense r-CSPs
Grigory Yaroslavtsev
We give new sublinear and parallel algorithms for the extensively studied problem of approximating n-variable r-CSPs (constraint satisfaction problems with constraints of arity r u…
Online Algorithms for Machine Minimization
Nikhil Devanur, Konstantin Makarychev, Debmalya Panigrahi +1
In this paper, we consider the online version of the machine minimization problem (introduced by Chuzhoy et al., FOCS 2004), where the goal is to schedule a set of jobs with releas…
Parallel Algorithms for Geometric Graph Problems
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak +1
We give algorithms for geometric graph problems in the modern parallel models inspired by MapReduce. For example, for the Minimum Spanning Tree (MST) problem over a set of points i…
The Round Complexity of Small Set Intersection
David P. Woodruff, Grigory Yaroslavtsev
The set disjointness problem is one of the most fundamental and well-studied problems in communication complexity. In this problem Alice and Bob hold sets , res…
Learning pseudo-Boolean k-DNF and Submodular Functions
Sofya Raskhodnikova, Grigory Yaroslavtsev
We prove that any submodular function f: {0,1}^n -> {0,1,...,k} can be represented as a pseudo-Boolean 2k-DNF formula. Pseudo-Boolean DNFs are a natural generalization of DNF repre…