Sublinear Algorithms Workshop

For over 20 years, extracting information from massive data has been a major challenge in various fields. How fast can we obtain meaningful information from large datasets? In this talk we will survey recent results on two classic problems: - Computing the mean of a set of points in R^d, for possibly large d. - Computing a clustering of a dataset given pairwise similarities between the data elements. We will see how this can be done in sublinear time without sacrificing much on the quality of the solution. The work is based on the following works: - Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn: NeurIPS 2021: -Correlation Clustering in Constant Many Parallel Rounds. Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski: ICML 2021

We study the nucleus decomposition problem, which has been shown to be useful in finding dense substructures in graphs. We present a novel parallel algorithm that is efficient both in theory and in practice. Our algorithm achieves a work complexity matching the best sequential algorithm while also having low depth (parallel running time), which significantly improves upon the only existing parallel nucleus decomposition algorithm (Sariyuce et al., PVLDB 2018). The key to the theoretical efficiency of our algorithm is a new lemma that bounds the amount of work done when peeling cliques from the graph, combined with the use of theoretically-efficient parallel algorithms for clique listing and bucketing. We introduce several new practical optimizations, including a new multi-level hash table structure to store information on cliques space-efficiently and a technique for traversing this structure cache-efficiently. On a 30-core machine with two-way hyper-threading on real-world graphs, we achieve up to a 55x speedup over the state-of-the-art parallel nucleus decomposition algorithm by Sariyuce et al., and up to a 40x self-relative parallel speedup. We are able to efficiently compute larger nucleus decompositions than prior work on several million-scale graphs for the first time.

Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. Given a set of points 𝑆 and a radius parameter 𝑟 > 0, the 𝑟 -near neighbor (𝑟 -NN) problem asks for a data structure that, given any query point 𝑞, returns a point 𝑝 within distance at most 𝑟 from 𝑞. In this paper, we study the 𝑟 -NN problem in the light of individual fairness and providing equal opportunities: all points that are within distance 𝑟 from the query should have the same probability to be returned. Locality sensitive hashing (LSH), the theoretically strongest approach to similarity search in high dimensions, does not provide such a fairness guarantee. In this work, we show that LSH based algorithms can be made fair, without a significant loss in efficiency. We propose several efficient data structures for the exact and approximate variants of the fair NN problem. Our approach works more generally for sampling uniformly from a sub-collection of sets of a given collection and can be used in a few other applications. This is a joint work with Martin Aumuller, Sariel Har-Peled, Rasum Pagh, and Francesco Silvestri.

The emergence of massive datasets signifies the importance of data efficiency algorithms. Feature engineering, a common method of reaching data efficiency, is one of the main ingredients in many machine learning pipelines. As an example of feature engineering, we review the role of combinatorial optimization techniques in designing subset selection algorithms. These methods focus on summarizing input features into concise sketches with provable performance guarantees. We look at some recent advances in submodular optimization and its potential application in this area. Another approach to data efficiency is to focus on the content of the features and develop compression techniques that retain the most important pieces of input data with regards to the classification tasks. >

Online learning with expert advice is a fundamental problem of sequential prediction. In this problem, the algorithm has access to a set of n "experts" who make predictions on each day. The goal on each day is to process these predictions, and make a prediction with the minimum cost. After making a prediction, the algorithm sees the actual outcome on that day, updates its state, and then moves on to the next day. An algorithm is judged by how well it does compared to the best expert in the set. The classical algorithm for this problem is the multiplicative weights algorithm. Variations of this algorithm have been applied to and optimized for a broad range of problems, including boosting an ensemble of weak-learners in machine learning, and approximately solving linear and semi-definite programs. However, every application, to our knowledge, relies on storing weights for every expert, and uses Omega(n) memory. There is little work on understanding the memory required to solve the online learning with expert advice problem (or run standard sequential prediction algorithms, such as multiplicative weights) in natural streaming models, which is important when the number of experts, as well as the number of days on which the experts make predictions, is large. We initiate the study of the learning with expert advice problem in the streaming setting, and show lower and upper bounds. Our lower bound for i.i.d., random order, and adversarial order streams uses a novel masking technique and distributional detection communication game to show a smooth trade-off for regret versus memory. Our upper bounds in adversarial and random-order streams show ways to run standard sequential prediction algorithms in rounds on small "pools" of experts, thus reducing the necessary memory. For random-order streams, we show that our upper bound is tight up to low order terms. Joint work with Vaidehi Srinivas, Ziyu (Neil) Xu, and Samson Zhou

This talk will discuss the fundamental statistical problem of estimating the mean of a distribution, as accurately as possible given samples from it. This problem arises both as a subcomponent of many algorithms, and also in practice as one of the most important data primitives when dealing with real-world data. While many variants and extensions of this problem have been proposed and analyzed, in this talk I will discuss two of the most iconic: 1) when the data comes from a real-valued distribution, and 2) when the data comes from a high-dimensional vector-valued distribution. In both cases, we achieve the first estimators whose accuracy is optimal to 1+o(1) factors, optimal in its dependence on the unknown (co-) variance of the underlying distribution, the number of samples n, and the desired confidence delta. I will highlight some of the crucial and novel analytical tools used in the analysis, and in particular, draw attention to a new "vector Bernstein inequality" which makes precise the intuition that sums of bounded independent random variables in increasingly high dimensions increasingly "adhere to a spherical shell". These results suggest several possible extensions in this large and active area of statistical estimation research. This talk is based on joint work with Jasper C.H. Lee.

We introduce the theory of distribution testing with a focus on tests for one-dimensional, structured distributions. In order to produce efficient testers, we introduce the theory of A_k distance and discuss the known results for optimal testers with respect to A_k distance, showing that it produces near-optimal testers for many distribution families.

In the metric Steiner Tree problem, we are given an n by n metric w on a set V of vertices along with a set T of k terminals, and the goal is to find a tree of minimum cost that contains all terminals in T. In this work, we initiate a study of the query complexity of the metric Steiner Tree problem. Specifically, if we desire an \alpha-approximate estimate of the metric Steiner Tree cost, how many entries need to be queried in the metric w? For the related minimum spanning tree (MST) problem, this question is well-understood. For any fixed \eps > 0, one can estimate the MST cost to within a (1+\eps)-factor using only \tilde O(n) queries, and this is known to be essentially tight. Note that this implies that a (2+\eps)-approximate estimate of Steiner Tree cost can be obtained with \tilde O(k) queries by simply applying the MST cost estimation algorithm on the metric induced by the terminals. Our first result shows that any (randomized) algorithm that estimates the Steiner Tree cost to within a (5/3-\eps)-factor requires \Omega(n^2) queries, even if k is a constant. This lower bound is in sharp contrast to an upper bound of O(nk) queries for computing a (5/3)-approximate Steiner Tree, which follows from previous work by Du and Zelikovsky. Our second main result, and the main technical contribution of this work, is a sublinear query algorithm for estimating the Steiner Tree cost to within a strictly better-than-2 factor. We give an algorithm that achieves this goal, with a query complexity of \tilde O(n^{12/7} + n^{6/7}k). Our estimation algorithm reduces this task to that of designing a sublinear query algorithm for a suitable set cover problem. We complement this result by showing an O(n + k^{6/5}) query lower bound for any algorithm that estimates Steiner Tree cost to a strictly better than 2 factor.