Grigory Yaroslavtsev

AAAI Conference 2024 Conference Paper

Approximation Scheme for Weighted Metric Clustering via Sherali-Adams

• Dmitrii Avdiukhin
• Vaggos Chatziafratis
• Konstantin Makarychev
• Grigory Yaroslavtsev

Motivated by applications to classification problems on metric data, we study Weighted Metric Clustering problem: given a metric d over n points and a k x k symmetric matrix A with non-negative entries, the goal is to find a k-partition of these points into clusters C1,...,Ck, while minimizing the sum of A[i,j] * d(u,v) over all pairs of clusters Ci and Cj and all pairs of points u from Ci and v from Cj. Specific choices of A lead to Weighted Metric Clustering capturing well-studied graph partitioning problems in metric spaces, such as Min-Uncut, Min-k-Sum, Min-k-Cut, and more. Our main result is that Weighted Metric Clustering admits a polynomial-time approximation scheme (PTAS). Our algorithm handles all the above problems using the Sherali-Adams linear programming relaxation. This subsumes several prior works, unifies many of the techniques for various metric clustering objectives, and yields a PTAS for several new problems, including metric clustering on manifolds and a new family of hierarchical clustering objectives. Our experiments on the hierarchical clustering objective show that it better captures the ground-truth structural information compared to the popular Dasgupta's objective.

NeurIPS Conference 2024 Conference Paper

Embedding Dimension of Contrastive Learning and $k$-Nearest Neighbors

• Dmitrii Avdiukhin
• Vaggos Chatziafratis
• Orr Fischer
• Grigory Yaroslavtsev

We study the embedding dimension of distance comparison data in two settings: contrastive learning and $k$-nearest neighbors ($k$-NN). In both cases, the goal is to find the smallest dimension $d$ of an $\ell_p$-space in which a given dataset can be represented. We show that the arboricity of the associated graphs plays a key role in designing embeddings. Using this approach, for the most frequently used $\ell_2$-distance, we get matching upper and lower bounds in both settings. In contrastive learning, we are given $m$ labeled samples of the form $(x_i, y_i^+, z_i^-)$ representing the fact that the positive example $y_i$ is closer to the anchor $x_i$ than the negative example $z_i$. We show that for representing such dataset in: - $\ell_2$: $d = \Theta(\sqrt{m})$ is necessary and sufficient. - $\ell_p$ for $p \ge 1$: $d = O(m)$ is sufficient and $d = \tilde \Omega(\sqrt{m})$ is necessary. - $\ell_\infty$: $d = O(m^{2/3})$ is sufficient and $d = \tilde \Omega(\sqrt{m})$ is necessary. We also give results for the more general scenario when $t$ negatives are allowed. In $k$-NN, for each of the $n$ data points we are given an ordered set of the closest $k$ points. We show that for preserving the ordering of the $k$-NN for every point in: - $\ell_2$: $d = \Theta(k)$ is necessary and sufficient. - $\ell_p$ for $p \ge 1$: $d = \tilde O(k^2)$ is sufficient and $d=\tilde \Omega(k)$ is necessary. - $\ell_\infty$: $d = \tilde \Omega(k)$ is necessary. Furthermore, if the goal is to not just preserve the ordering of the $k$-NN but also keep them as the nearest neighbors then $d = \tilde O (\mathrm{poly}(k))$ suffices in $\ell_p$ for $p \ge 1$.

ICLR Conference 2024 Conference Paper

Optimal Sample Complexity of Contrastive Learning

• Noga Alon
• Dmitrii Avdiukhin
• Dor Elboim
• Orr Fischer
• Grigory Yaroslavtsev

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 sample complexity of contrastive learning, i.e. the minimum number of labeled tuples sufficient for getting high generalization accuracy. We give tight bounds on the sample complexity in a variety of settings, focusing on arbitrary distance functions, $\ell_p$-distances, and tree metrics. Our main result is an (almost) optimal bound on the sample complexity of learning $\ell_p$-distances for integer $p$. For any $p \ge 1$, we show that $\tilde \Theta(nd)$ labeled tuples are necessary and sufficient for learning $d$-dimensional representations of $n$-point datasets. Our results hold for an arbitrary distribution of the input samples and are based on giving the corresponding bounds on the Vapnik-Chervonenkis/Natarajan dimension of the associated problems. We further show that the theoretical bounds on sample complexity obtained via VC/Natarajan dimension can have strong predictive power for experimental results, in contrast with the folklore belief about a substantial gap between the statistical learning theory and the practice of deep learning.

IJCAI Conference 2023 Conference Paper

HOUDINI: Escaping from Moderately Constrained Saddles

• Dmitrii Avdiukhin
• Grigory Yaroslavtsev

We give polynomial time algorithms for escaping from high-dimensional saddle points under a moderate number of constraints. Given gradient access to a smooth function, we show that (noisy) gradient descent methods can escape from saddle points under a logarithmic number of inequality constraints. While analogous results exist for unconstrained and equality-constrained problems, we make progress on the major open question of convergence to second-order stationary points in the case of inequality constraints, without reliance on NP-oracles or altering the definitions to only account for certain constraints. Our results hold for both regular and stochastic gradient descent.

AAAI Conference 2023 Conference Paper

Tree Learning: Optimal Sample Complexity and Algorithms

• Dmitrii Avdiukhin
• Grigory Yaroslavtsev
• Danny Vainstein
• Orr Fischer
• Sauman Das
• Faraz Mirza

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 collection of data tuples labeled according to their hierarchical structure. The smallest number of such tuples required in order to be able to accurately label subsequent tuples is of interest for data collection in machine learning. We present optimal sample complexity bounds for this problem in several learning settings, including (agnostic) PAC learning and online learning. Our results are based on tight bounds of the Natarajan and Littlestone dimensions of the associated problem. The corresponding tree classifiers can be constructed efficiently in near-linear time.

NeurIPS Conference 2021 Conference Paper

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 multiple machines, communication typically becomes a bottleneck in the distributed setting. Gradient compression methods can be used to alleviate this problem, and a recent line of work shows that SGD augmented with gradient compression converges to an $\varepsilon$-first-order stationary point. In this paper we extend these results to convergence to an $\varepsilon$-second-order stationary point ($\varepsilon$-SOSP), which is to the best of our knowledge the first result of this type. In addition, we show that, when the stochastic gradient is not Lipschitz, compressed SGD with RandomK compressor converges to an $\varepsilon$-SOSP with the same number of iterations as uncompressed SGD [Jin et al. ,2021] (JACM), while improving the total communication by a factor of $\tilde \Theta(\sqrt{d} \varepsilon^{-3/4})$, where $d$ is the dimension of the optimization problem. We present additional results for the cases when the compressor is arbitrary and when the stochastic gradient is Lipschitz.

AAAI Conference 2021 Conference Paper

Objective-Based Hierarchical Clustering of Deep Embedding Vectors

• Stanislav Naumov
• Grigory Yaroslavtsev
• Dmitrii Avdiukhin

We initiate a comprehensive experimental study of objectivebased hierarchical clustering methods on massive datasets consisting of deep embedding vectors from computer vision and NLP applications. This includes a large variety of image embedding (ImageNet, ImageNetV2, NaBirds), word embedding (Twitter, Wikipedia), and sentence embedding (SST-2) vectors from several popular recent models (e. g. ResNet, ResNext, Inception V3, SBERT). Our study includes datasets with up to 4. 5 million entries with embedding dimensions up to 2048. In order to address the challenge of scaling up hierarchical clustering to such large datasets we propose a new practical hierarchical clustering algorithm B++&C. It gives a 5%/20% improvement on average for the popular Moseley-Wang (MW) / Cohen-Addad et al. (CKMM) objectives (normalized) compared to a wide range of classic methods and recent heuristics. We also introduce a theoretical algorithm B2SAT&C which achieves a 0. 74-approximation for the CKMM objective in polynomial time. This is the first substantial improvement over the trivial 2/3-approximation achieved by a random binary tree. Prior to this work, the best poly-time approximation of ≈ 2/3 + 0. 0004 was due to Charikar et al. (SODA’19).

ICML Conference 2018 Conference Paper

Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under 𝓁 p Distances

• Grigory Yaroslavtsev
• Adithya Vadapalli

We present first massively parallel (MPC) algorithms and hardness of approximation results for computing Single-Linkage Clustering of n input d-dimensional vectors under Hamming, $\ell_1, \ell_2$ and $\ell_\infty$ distances. All our algorithms run in O(log n) rounds of MPC for any fixed d and achieve (1+\epsilon)-approximation for all distances (except Hamming for which we show an exact algorithm). We also show constant-factor inapproximability results for o(\log n)-round algorithms under standard MPC hardness assumptions (for sufficiently large dimension depending on the distance used). Efficiency of implementation of our algorithms in Apache Spark is demonstrated through experiments on the largest available vector datasets from the UCI machine learning repository exhibiting speedups of several orders of magnitude.

SODA Conference 2016 Conference Paper

Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model

• Sepehr Assadi
• Sanjeev Khanna
• Yang Li 0025
• Grigory Yaroslavtsev

We study the problem of finding an approximate maximum matching in two closely related computational models, namely, the dynamic graph streaming model and the simultaneous multi-party communication model. In the dynamic graph streaming model, the input graph is revealed as a stream of edge insertions and deletions, and the goal is to design a small space algorithm to approximate the maximum matching. In the simultaneous model, the input graph is partitioned across k players, and the goal is to design a protocol where the k players simultaneously send a small-size message to a coordinator, and the coordinator computes an approximate matching. Dynamic graph streams. We resolve the space complexity of single-pass turnstile streaming algorithms for approximating matchings by showing that for any ∊ > 0, ⊝( n 2–3 e ) space is both sufficient and necessary (up to polylogarithmic factors) to compute an n ∊-approximate matching; here n denotes the number of vertices in the input graph. The simultaneous communication model. Our results for dynamic graph streams also resolve the (per-player) simultaneous communication complexity for approximating matchings in the edge partition model. For the vertex partition model, we design new randomized and deterministic protocols for k players to achieve an α -approximation. Specifically, for, we provide a randomized protocol with total communication of O ( nk / α 2 ) and a deterministic protocol with total communication of O ( nk / α ). Both these bounds are tight. Our work generalizes the results established by Dobzinski et al. (STOC 2014) for the special case of k = n. Finally, for the case of, we establish a new lower bound on the simultaneous communication complexity which is super-linear in n.

STOC Conference 2015 Conference Paper

Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs

• Shuchi Chawla 0001
• Konstantin Makarychev
• Tselil Schramm
• Grigory Yaroslavtsev

We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality gaps: For complete graphs our approximation is 2.06 - ε, which almost matches the previously known integrality gap of 2. For complete k-partite graphs our approximation is 3. We also show a matching integrality gap. For complete graphs with edge weights satisfying triangle inequalities and probability constraints, our approximation is 1.5, and we show an integrality gap of 1.2. Our results improve a long line of work on approximation algorithms for correlation clustering in complete graphs, previously culminating in a ratio of 2.5 for the complete case by Ailon, Charikar and Newman (JACM'08). In the weighted complete case satisfying triangle inequalities and probability constraints, the same authors give a 2-approximation; for the bipartite case, Ailon, Avigdor-Elgrabli, Liberty and van Zuylen give a 4-approximation (SICOMP'12).

STOC Conference 2014 Conference Paper

L p -testing

• Piotr Berman
• Sofya Raskhodnikova
• Grigory Yaroslavtsev

STOC Conference 2014 Conference Paper

Parallel algorithms for geometric graph problems

• Alexandr Andoni
• Aleksandar Nikolov
• Krzysztof Onak
• Grigory Yaroslavtsev

We give algorithms for geometric graph problems in the modern parallel models such as MapReduce. For example, for the Minimum Spanning Tree (MST) problem over a set of points in the two-dimensional space, our algorithm computes a (1 + ε )-approximate MST. Our algorithms work in a constant number of rounds of communication, while using total space and communication proportional to the size of the data (linear space and near linear time algorithms). In contrast, for general graphs, achieving the same result for MST (or even connectivity) remains a challenging open problem [9], despite drawing significant attention in recent years.

I&C Journal 2013 Journal Article

Approximation algorithms for spanner problems and Directed Steiner Forest

• Piotr Berman
• Arnab Bhattacharyya
• Konstantin Makarychev
• Sofya Raskhodnikova
• Grigory Yaroslavtsev

We present an O ( n log n ) -approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, given a graph G = ( V, E ) with nonnegative edge lengths d: E → R ⩾ 0 and a stretch k ⩾ 1, a subgraph H = ( V, E H ) is a k-spanner of G if for every edge ( s, t ) ∈ E, the graph H contains a path from s to t of length at most k ⋅ d ( s, t ). The previous best approximation ratio was O ˜ ( n 2 / 3 ), due to Dinitz and Krauthgamer (STOC ʼ11). We also improve the approximation ratio for the important special case of directed 3-spanners with unit edge lengths from O ˜ ( n ) to O ( n 1 / 3 log n ). The best previously known algorithms for this problem are due to Berman, Raskhodnikova and Ruan (FSTTCS ʼ10) and Dinitz and Krauthgamer. The approximation ratio of our algorithm almost matches Dinitz and Krauthgamerʼs lower bound for the integrality gap of a natural linear programming relaxation. Our algorithm directly implies an O ( n 1 / 3 log n ) -approximation for the 3-spanner problem on undirected graphs with unit lengths. An easy O ( n ) -approximation algorithm for this problem has been the best known for decades. Finally, we consider the Directed Steiner Forest problem: given a directed graph with edge costs and a collection of ordered vertex pairs, find a minimum-cost subgraph that contains a path between every prescribed pair. We obtain an approximation ratio of O ( n 2 / 3 + ϵ ) for any constant ϵ > 0, which improves the O ( n ϵ ⋅ min ( n 4 / 5, m 2 / 3 ) ) ratio due to Feldman, Kortsarz and Nutov (JCSSʼ12).

SODA Conference 2013 Conference Paper

Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching

• Marco Molinaro 0001
• David P. Woodruff
• Grigory Yaroslavtsev

A direct sum theorem for two parties and a function f states that the communication cost of solving k copies of f simultaneously with error probability 1/3 is at least k · R 1/3 ( f ), where R 1/3 ( f ) is the communication required to solve a single copy of f with error probability 1/3. We improve this for a natural family of functions f, showing that the 1-way communication required to solve k copies of f simultaneously with probability 2/3 is Ω( k · R 1/ k ( f )). Since R 1/ k ( f ) may be as large as Ω( R 1/3 ( f ) · log k ), we asymptotically beat the direct sum bound for such functions, showing that the trivial upper bound of solving each of the k copies of f with probability 1 − O (1/ k ) and taking a union bound is optimal! In order to achieve this, our direct sum involves a novel measure of information cost which allows a protocol to abort with constant probability, and otherwise must be correct with very high probability. Moreover, for the functions considered, we show strong lower bounds on the communication cost of protocols with these relaxed guarantees; indeed, our lower bounds match those for protocols that are not allowed to abort. In the distributed and streaming models, where one wants to be correct not only on a single query, but simultaneously on a sequence of n queries, we obtain optimal lower bounds on the communication or space complexity. Lower bounds obtained from our direct sum result show that a number of techniques in the sketching literature are optimal, including the following: (JL transform) Lower bound of on the dimension of (oblivious) Johnson-Lindenstrauss transforms. (ℓ p -estimation) Lower bound for the size of encodings of n vectors in [± M ] d that allow ℓ 1 or ℓ 2 -estimation of. (Matrix sketching) Lower bound of on the dimension of a matrix sketch S satisfying the entrywise guarantee |( ASS T B ) i, j − ( AB ) i, j | ≤ ε‖ A i ‖2‖B j ‖ 2. (Database joins) Lower bound of for sketching frequency vectors of n tables in a database, each with M records, in order to allow join size estimation.

SODA Conference 2013 Conference Paper

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 2 k -DNF formula. Pseudo-Boolean DNFs are a natural generalization of DNF representation for functions with integer range. Each term in such a formula has an associated integral constant. We show that an analog of Håstad's switching lemma holds for pseudo-Boolean k -DNFs if all constants associated with the terms of the formula are bounded. This allows us to generalize Mansour's PAC-learning algorithm for k -DNFs to pseudo-Boolean k -DNFs, and hence gives a PAC-learning algorithm with membership queries under the uniform distribution for submodular functions of the form f: {0, 1} n → {0, 1, …, k }. Our algorithm runs in time polynomial in n, k O ( k log k /ε) and log(1/δ) and works even in the agnostic setting. The line of previous work on learning submodular functions [Balcan, Harvey (STOC ′11), Gupta, Hardt, Roth, Ullman (STOC ′11), Cheraghchi, Klivans, Kothari, Lee (SODA ′12)] implies only n O ( k ) query complexity for learning submodular functions in this setting, for fixed ε and δ. Our learning algorithm implies a property tester for submodularity of functions f: {0, 1} n → {0, …, k } with query complexity polynomial in n for k = O ((log n /log log n ) 1/2 ) and constant proximity parameter ε.

SAT Conference 2009 Conference Paper

Finding Efficient Circuits Using SAT-Solvers

• Arist Kojevnikov
• Alexander S. Kulikov
• Grigory Yaroslavtsev

Abstract In this paper we report preliminary results of experiments with finding efficient circuits (over binary bases) using SAT-solvers. We present upper bounds for functions with constant number of inputs as well as general upper bounds that were found automatically. We focus mainly on MOD-functions. Besides theoretical interest, these functions are also interesting from a practical point of view as they are the core of the residue number system. In particular, we present a circuit of size 3 n + c over the full binary basis computing \({\rm MOD}_3^n\).