9 citations · 10 across the 8 of their papers we have counts for
9 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…
"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…
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…