15 citations · 58 across the 19 of their papers we have counts for
7 papers · 1 filter
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…