Benjamin Coleman, Anshumali Shrivastava, Richard G. Baraniuk
2019-02-18
We present the first sublinear memory sketch which can be queried to find the
nearest neighbors in a dataset. Our online sketching algorithm can compress an -element dataset to a sketch of size in time, where when the query satisfies a data-dependent near-neighbor stability condition. We achieve data-dependent sublinear space by combining recent advances in locality sensitive hashing (LSH)-based estimators with compressed sensing. Our results shed new light on the memory-accuracy tradeoff for near-neighbor search. The techniques presented reveal a deep connection between the fundamental compressed sensing (or heavy hitters) recovery problem and near-neighbor search, leading to new insight for geometric search problems and implications for sketching algorithms.
Oren Mangoubi, Nisheeth K. Vishnoi
2019-02-22
The Langevin Markov chain algorithms are widely deployed methods to sample from distributions in challenging high-dimensional and non-convex statistics and machine learning applications. Despite this, current bounds for the Langevin algorithms are slower than those of competing algorithms in many important situations, for instance when sampling from weakly log-concave distributions, or when sampling or optimizing non-convex log-densities. In this paper, we obtain improved bounds in many of these situations, showing that the Metropolis-adjusted Langevin algorithm (MALA) is faster than the best bounds for its competitor algorithms when the target distribution satisfies weak third- and fourth- order regularity properties associated with the input data. In many settings, our regularity conditions are weaker than the usual Euclidean operator norm regularity properties, allowing us to show faster bounds for a much larger class of distributions than would be possible with the usual Euclidean operator norm approach, including in statistics and machine learning applications where the data satisfy a certain incoherence condition. In particular, we show that using our regularity conditions one can obtain faster bounds for applications which include sampling problems in Bayesian logistic regression with weakly convex priors, and the nonconvex optimization problem of learning linear classifiers with zero-one loss functions. Our main technical contribution in this paper is our analysis of the Metropolis acceptance probability of MALA in terms of its "energy-conservation error," and our bound for this error in terms of third- and fourth- order regularity conditions. Our combination of this higher-order analysis of the energy conservation error with the conductance method is key to obtaining bounds which have a sub-linear dependence on the dimension
in the non-strongly logconcave setting.
Jarno Alanko, Alberto Policriti, Nicola Prezza
2019-02-04
Indexing strings via prefix (or suffix) sorting is, arguably, one of the most successful algorithmic techniques developed in the last decades. String indexes allow solving efficiently a large number of problems, including counting and locating occurrences of a pattern in the indexed string. Can indexing be extended to languages? In this paper, we approach the problem by combining techniques from string processing (specifically, prefix-sorting) and automata theory (specifically, DFA minimization). Our main contributions are algorithms that, given a finite language represented either explicitly as a set of strings or implicitly as an acyclic DFA, generate the minimum accepting DFA that can be prefix-sorted and thus indexed for linear-time pattern matching queries. In order to achieve this result we use the recent notion of Wheeler graph [Gagie et al., TCS 2017], which extends naturally the concept of prefix sorting to labeled graphs.
Sepehr Assadi, Yu Chen, Sanjeev Khanna
2019-04-09
We present new lower bounds that show that a polynomial number of passes are necessary for solving some fundamental graph problems in the streaming model of computation. For instance, we show that any streaming algorithm that finds a weighted minimum
- cut in an -vertex undirected graph requires space unless it makes passes over the stream. To prove our lower bounds, we introduce and analyze a new four-player communication problem that we refer to as the hidden-pointer chasing problem. This is a problem in spirit of the standard pointer chasing problem with the key difference that the pointers in this problem are hidden to players and finding each one of them requires solving another communication problem, namely the set intersection problem. Our lower bounds for graph problems are then obtained by reductions from the hidden-pointer chasing problem. Our hidden-pointer chasing problem appears flexible enough to find other applications and is therefore interesting in its own right. To showcase this, we further present an interesting application of this problem beyond streaming algorithms. Using a reduction from hidden-pointer chasing, we prove that any algorithm for submodular function minimization needs to make value queries to the function unless it has a polynomial degree of adaptivity.
Adrien Chan-Hon-Tong
2019-01-22
This short paper presents an algorithm based on simple projections and linear feasibility (
) queries which solves both linear programming ( ), and, support vector margin ( ). In addition, this algorithm is strongly polynomial on special instance of both linear program and support vector margin, characterized by a similar convex hull property. Thus, this algorithm could be interesting as a link between all these four notions: linear feasibility, linear programming, support vector margin and convex hull.
Shunsuke Inenaga
2019-04-09
The suffix tree, DAWG, and CDAWG are fundamental indexing structures of a string, with a number of applications in bioinformatics, information retrieval, data mining, etc. An edge-labeled rooted tree (trie) is a natural generalization of a string. Breslauer [TCS 191(1-2): 131-144, 1998] proposed the suffix tree for a backward trie, where the strings in the trie are read in the leaf-to-root direction. In contrast to a backward trie, we call a usual trie as a forward trie. Despite a few follow-up works after Breslauer's paper, indexing forward/backward tries is not well understood yet. In this paper, we show a full perspective on the sizes of indexing structures such as suffix trees, DAWGs, and CDAWGs for forward and backward tries. In particular, we show that the size of the DAWG for a forward trie with
nodes is , where is the number of distinct characters in the trie. This becomes for a large alphabet. Still we show that there is a compact -space representation of the DAWG for a forward trie over any alphabet, and present an -time -space algorithm to construct such a representation of the DAWG for a growing forward trie.
Tomasz Krawczyk
2019-04-09
Circular-arc graphs are intersection graphs of arcs on the circle. The aim of our work is to present a polynomial time algorithm testing whether two circular-arc graphs are isomorphic. To accomplish our task we construct decomposition trees, which are the structures representing all normalized intersection models of circular-arc graphs. Normalized models reflect the neighbourhood relation in circular-arc graphs and can be seen as their canonical representations; in particular, every intersection model can be easily transformed into a normalized one. Our work adapts and appropriately extends the previous work on the similar topic done by Hsu [\emph{SIAM J. Comput. 24(3), 411--439, (1995)}]. In his work, Hsu developed decomposition trees representing all normalized models of circular-arc graphs. However due to the counterexample given in [\emph{Discrete Math. Theor. Comput. Sci., 15(1), 157--182, 2013}], his decomposition trees can not be used by algorithms testing isomorphism of circular-arc graphs.
Xianrui Meng, Dimitrios Papadopoulos, Alina Oprea, Nikos Triandopoulos
2019-04-09
Machine Learning (ML) is widely used for predictive tasks in a number of critical applications. Recently, collaborative or federated learning is a new paradigm that enables multiple parties to jointly learn ML models on their combined datasets. Yet, in most application domains, such as healthcare and security analytics, privacy risks limit entities to individually learning local models over the sensitive datasets they own. In this work, we present the first formal study for privacy-preserving collaborative hierarchical clustering, overall featuring scalable cryptographic protocols that allow two parties to privately compute joint clusters on their combined sensitive datasets. First, we provide a formal definition that balances accuracy and privacy, and we present a provably secure protocol along with an optimized version for single linkage clustering. Second, we explore the integration of our protocol with existing approximation algorithms for hierarchical clustering, resulting in a protocol that can efficiently scale to very large datasets. Finally, we provide a prototype implementation and experimentally evaluate the feasibility and efficiency of our approach on synthetic and real datasets, with encouraging results. For example, for a dataset of one million records and 10 dimensions, our optimized privacy-preserving approximation protocol requires 35 seconds for end-to-end execution, just 896KB of communication, and achieves 97.09% accuracy.
Danupon Nanongkai, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
2019-04-09
Vertex connectivity a classic extensively-studied problem. Given an integer
, its goal is to decide if an -node -edge graph can be disconnected by removing vertices. Although a linear-time algorithm was postulated since 1974 [Aho, Hopcroft and Ullman], and despite its sibling problem of edge connectivity being resolved over two decades ago [Karger STOC'96], so far no vertex connectivity algorithms are faster than time even for and . In the simplest case where and , the bound dates five decades back to [Kleitman IEEE Trans. Circuit Theory'69]. For general and , the best bound is . In this paper, we present a randomized Monte Carlo algorithm with time for any . This gives the {\em first subquadratic time} bound for any and improves all above classic bounds for all . We also present a new randomized Monte Carlo -approximation algorithm that is strictly faster than the previous Henzinger's 2-approximation algorithm [J. Algorithms'97] and all previous exact algorithms. The key to our results is to avoid computing single-source connectivity, which was needed by all previous exact algorithms and is not known to admit time. Instead, we design the first {\em local algorithm} for computing vertex connectivity; without reading the whole graph, our algorithm can find a separator of size at most or certify that there is no separator of size at most `near' a given seed node.
Nikolaj Tatti
2019-04-09
Discovering the underlying structure of a given graph is one of the fundamental goals in graph mining. Given a graph, we can often order vertices in a way that neighboring vertices have a higher probability of being connected to each other. This implies that the edges form a band around the diagonal in the adjacency matrix. Such structure may rise for example if the graph was created over time: each vertex had an active time interval during which the vertex was connected with other active vertices. The goal of this paper is to model this phenomenon. To this end, we formulate an optimization problem: given a graph and an integer
, we want to order graph vertices and partition the ordered adjacency matrix into bands such that bands closer to the diagonal are more dense. We measure the goodness of a segmentation using the log-likelihood of a log-linear model, a flexible family of distributions containing many standard distributions. We divide the problem into two subproblems: finding the order and finding the bands. We show that discovering bands can be done in polynomial time with isotonic regression, and we also introduce a heuristic iterative approach. For discovering the order we use Fiedler order accompanied with a simple combinatorial refinement. We demonstrate empirically that our heuristic works well in practice.
