We provide improved upper and lower bounds for the Min-Sum-Radii (MSR) and Min-Sum-Diameters (MSD) clustering problems with a bounded number of clusters k. In particular, we propose an exact MSD algorithm with running-time n^O(k). We also provide (1 + Ɛ) approximation algorithms for both MSR and MSD with running-times of O(kn) + (1/Ɛ)^O(dk) in metrics spaces of doubling dimension d. Our algorithms extend to k-center, improving upon previous results, and to α-MSR, where radii are raised to the α power for α > 1. For α-MSD we prove an exponential time ETH-based lower bound for α > log 3. All algorithms can also be modified to handle outliers. Moreover, we can extend the results to variants that observe fairness constraints, as well as to the general framework of mergeable clustering, which includes many other popular clustering variants. We complement these upper bounds with ETH-based lower bounds for these problems, in particular proving that n^O(k) time is tight for MSR and α-MSR even in doubling spaces, and that 2^o(k) bounds are impossible for MSD.

We present a refined construction of hierarchical probabilistic partitions with novel properties, substantially stronger than previously known. Our construction provides a family of hierarchical partitions enabling fast dynamic programming algorithms, by guaranteeing that given a sparse set of balls, each cell of the hierarchical partition intersects only a small number of balls. The number of balls intersecting a cell is bounded solely as a function of the padding parameter of the partition (which is bounded in particular by the doubling dimension). This is in contrast to standard guarantees for probabilistic partitions which holds only in expectation. Additionally, each cell of our partition has a significantly smaller description than in previous constructions. These novel partition properties allow faster dynamic programs for a wide spectrum of fundamental problems defined by inherent or implicit sparsity. Among our main applications highlighting the utility of the novel properties are two well-studied clustering problems: min-sum radii (MSR) and min-sum diameters (MSD) clustering. The input to both these problems is a metric space and an integer$k$, and the goal is to partition the space into$k$clusters so as to minimize the sum of radii or diameters of the clusters, respectively. We apply our construction to give dramatically improved exact and approximation algorithms for these problems in Euclidean and doubling spaces, planar graphs, and more general settings. In particular, we obtain for these problems the first PTAS for doubling spaces, improving and generalizing upon the time bounds known for Euclidean space, even achieving linear time algorithms for fixed parameter$k$. We also obtain the first PTAS for MSR for all metrics of bounded padding parameter, including planar and minor excluded metrics. Moreover, our results extend to constrained variants such as fair MSR and mergeable MSR, dramatically improving upon the best known results on these problems in low dimension. Our methods also extend to other clustering problems, including$\alpha$-MSR and$\alpha$-MSD (where the measure is the sum of radii or diameters raised to power of$\alpha$), as well as aversion clustering, providing in similar settings the first QPTAS and first fixed parameter PTAS for these problems. Moreover, many of our clustering results extend to the corresponding clustering problems with outliers. Our construction applies as well to a wide range of network design problems possessing inherent sparsity properties in doubling spaces. Notably, we can apply our method to dramatically improve upon the best known bounds for the traveling salesman (TSP) and Steiner tree problems in doubling spaces. Similarly, we significantly improve upon the best known runtimes for Steiner forest, TSP with neighborhoods, prize collecting TSP, and 2-ECSS (two edge-connected spanning subgraph), all in doubling spaces. Our new constructions of hierarchical probabilistic partitions present a major simplification of previous methods, and provide a more natural and useful tool for future applications.

The problem of nearest neighbor condensing has enjoyed a long history of study, both in its theoretical and practical aspects. In this paper, we introduce the problem of weighted distance nearest neighbor condensing, where one assigns weights to each point of the condensed set, and then new points are labeled based on their weighted distance nearest neighbor in the condensed set. We study the theoretical properties of this new model, and show that it can produce dramatically better condensing than the standard nearest neighbor rule, yet is characterized by generalization bounds almost identical to the latter. We then suggest a condensing heuristic for our new problem. We demonstrate Bayes consistency for this heuristic, and also show promising empirical results.

We initiate a program of average smoothness analysis for efficiently learning real-valued functions on metric spaces. Rather than using the Lipschitz constant as the regularizer, we define a local slope at each point and gauge the function complexity as the average of these values. Since the mean can be dramatically smaller than the maximum, this complexity measure can yield considerably sharper generalization bounds --- assuming that these admit a refinement where the Lipschitz constant is replaced by our average of local slopes. Our first major contribution is to obtain just such distribution-sensitive bounds. This required overcoming a number of technical challenges, perhaps the most formidable of which was bounding the empirical covering numbers, which can be much worse-behaved than the ambient ones. Our combinatorial results are accompanied by efficient algorithms for smoothing the labels of the random sample, as well as guarantees that the extension from the sample to the whole space will continue to be, with high probability, smooth on average. Along the way we discover a surprisingly rich combinatorial and analytic structure in the function class we define.

Abstract We introduce a new embedding technique based on a nested barycentric coordinate system. We show that our embedding can be used to transform the problems of polyhedron approximation, piecewise linear classification and convex regression into one of finding a linear classifier or regressor in a higher dimensional (but nevertheless quite sparse) representation. Our embedding maps a piecewise linear function into an everywhere-linear function, and allows us to invoke well-known algorithms for the latter problem to solve the former. We explain the applications of our embedding to the problems of approximating separating polyhedra—in fact, it can approximate any convex body and unions of convex bodies—as well as to classification by separating polyhedra, and to piecewise linear regression.

We present an improved algorithm forquasi-properlylearning convex polyhedra in the realizable PAC setting from data with a margin. Our learning algorithm constructs a consistent polyhedron as an intersection of about$t \log t$halfspaces with constant-size margins in time polynomial in$t$(where$t$is the number of halfspaces forming an optimal polyhedron). We also identify distinct generalizations of the notion of margin from hyperplanes to polyhedra and investigate how they relate geometrically; this result may have ramifications beyond the learning setting.

We introduce a new embedding technique based on barycentric coordinate system. We show that our embedding can be used to transforms the problem of polytope approximation into that of finding a linear classifier in a higher (but nevertheless quite sparse) dimensional representation. This embedding in effect maps a piecewise linear function into a single linear function, and allows us to invoke well-known algorithms for the latter problem to solve the former. We demonstrate that our embedding has applications to the problems of approximating separating polytopes – in fact, it can approximate any convex body and multiple convex bodies – as well as to classification by separating polytopes and piecewise linear regression.

We initiate a program of average smoothness analysis for efficiently learning real-valued functions on metric spaces. Rather than using the Lipschitz constant as the regularizer, we define a local slope at each point and gauge the function complexity as the average of these values. Since the mean can be dramatically smaller than the maximum, this complexity measure can yield considerably sharper generalization bounds — assuming that these admit a refinement where the Lipschitz constant is replaced by our average of local slopes. In addition to the usual average, we also examine a “weak” average that is more forgiving and yields a much wider function class. Our first major contribution is to obtain just such distribution-sensitive bounds. This required overcoming a number of technical challenges, perhaps the most formidable of which was bounding the {\em empirical} covering numbers, which can be much worse-behaved than the ambient ones. Our combinatorial results are accompanied by efficient algorithms for smoothing the labels of the random sample, as well as guarantees that the extension from the sample to the whole space will continue to be, with high probability, smooth on average. Along the way we discover a surprisingly rich combinatorial and analytic structure in the function class we define.

We give an algorithm that computes a (1+є)-approximate Steiner forest in near-linear time n · 2(1/є)O(ddim2) (loglogn)2, where ddim is the doubling dimension of the metric space. This improves upon the best previous result due to Chan et al. (SIAM J. Comput. 4 (2018)), who gave a runtime of about n2O(ddim) · 2(ddim/є)O(ddim) √logn. For Steiner tree our methods achieve an even better runtime n (logn)(1/є)O(ddim2).

We investigate for which metric spaces the performance of distance labeling and of ℓ∞-embeddings differ, and how significant can this difference be. Recall that a distance labeling is a distributed representation of distances in a metric space (X, d), where each point x ∊ X is assigned a succinct label, such that the distance between any two points x, y ∊ X can be approximated given only their labels. A highly structured special case is an embedding into ℓ∞, where each point x ∊ X is assigned a vector f (x) such that ‖f(x)−f (y)‖∞ is approximately d(x, y). The performance of a distance labeling or an ℓ∞-embedding is measured via its distortion and its label-size/dimension. We also study the analogous question for the prioritized versions of these two measures. Here, a priority order π = (x1, …, xn) of the point set X is given, and higher-priority points should have shorter labels. Formally, a distance labeling has prioritized label-size α(.) if every xj has label size at most α(j). Similarly, an embedding f: X → ℓ∞ has prioritized dimension α(·) if f (xj) is non-zero only in the first α(j) coordinates. In addition, we compare these their prioritized measures to their classical (worst-case) versions. We answer these questions in several scenarios, uncovering a surprisingly diverse range of behaviors. First, in some cases labelings and embeddings have very similar worst-case performance, but in other cases there is a huge disparity. However in the prioritized setting, we most often find a strict separation between the performance of labelings and embeddings. And finally, when comparing the classical and prioritized settings, we find that the worst-case bound for label size often “translates” to a prioritized one, but also a surprising exception to this rule.

We present improved algorithm for properly learning convex polytopes in the realizable PAC setting from data with a margin. Our learning algorithm constructs a consistent polytope as an intersection of about t log t halfspaces with margins in time polynomial in t (where t is the number of halfspaces forming an optimal polytope). We also identify distinct generalizations of the notion of margin from hyperplanes to polytopes and investigate how they relate geometrically; this result may be of interest beyond the learning setting.

We present the first sample compression algorithm for nearest neighbors with non-trivial performance guarantees. We complement these guarantees by demonstrating almost matching hardness lower bounds, which show that our performance bound is nearly optimal. Our result yields new insight into margin-based nearest neighbor classification in metric spaces and allows us to significantly sharpen and simplify existing bounds. Some encouraging empirical results are also presented.

We initiate the rigorous study of classification in semimetric spaces, which are point sets with a distance function that is non-negative and symmetric, but need not satisfy the triangle inequality. We define the density dimension dens and discover that it plays a central role in the statistical and algorithmic feasibility of learning in semimetric spaces. We compute this quantity for several widely used semimetrics and present nearly optimal sample compression algorithms, which are then used to obtain generalization guarantees, including fast rates. Our claim of near-optimality holds in both computational and statistical senses. When the sample has radius $R$ and margin $\gamma$, we show that it can be compressed down to roughly $d=(R/\gamma)^{\text{dens}}$ points, and further that finding a significantly better compression is algorithmically intractable unless P=NP. This compression implies generalization via standard Occam-type arguments, to which we provide a nearly matching lower bound.

We present a framework for performing efficient regression in general metric spaces. Roughly speaking, our regressor predicts the value at a new point by computing an approximate Lipschitz extension- the smoothest function consistent with the observed data- after performing structural risk minimization to avoid overfitting. We obtain finite-sample risk bounds with minimal structural and noise assumptions, and a natural runtime-precision tradeoff. The offline (learning) and online (prediction) stages can be solved by convex programming, but this naive approach has runtime complexity O(n3), which is prohibitive for large data sets. We design instead a regression algorithm whose speed and generalization performance depend on the intrinsic dimension of the data, to which the algorithm adapts. While our main innovation is algorithmic, the statistical results may also be of independent

We initiate the rigorous study of classification in semimetric spaces, which are point sets with a distance function that is non-negative and symmetric, but need not satisfy the triangle inequality. We define the \em density dimension \dens and discover that it plays a central role in the statistical and algorithmic feasibility of learning in semimetric spaces. We compute this quantity for several widely used semimetrics and present nearly optimal sample compression algorithms, which are then used to obtain generalization guarantees, including fast rates. Our claim of near-optimality holds in both computational and statistical senses. When the sample has radius R and margin γ, we show that it can be compressed down to roughly d=(R/γ)^\dens points, and further that finding a significantly better compression is algorithmically intractable unless P=NP. This compression implies generalization via standard Occam-type arguments, to which we provide a nearly matching lower bound.

For Euclidean space (l_2), there exists the powerful dimension reduction transform of Johnson and Lindenstrauss [Conf. in modern analysis and probability, AMS 1984], with a host of known applications. Here, we consider the problem of dimension reduction for all l_p spaces 1<p<2. Although strong lower bounds are known for dimension reduction in l_1, Ostrovsky and Rabani [JACM 2002] successfully circumvented these by presenting an l_1 embedding that maintains fidelity in only a bounded distance range, with applications to clustering and nearest neighbor search. However, their embedding techniques are specific to l_1 and do not naturally extend to other norms. In this paper, we apply a range of advanced techniques and produce bounded range dimension reduction embeddings for all of 1<p<2, thereby demonstrating that the approach initiated by Ostrovsky and Rabani for l_1 can be extended to a much more general framework. We also obtain improved bounds in terms of the intrinsic dimensionality. As a result we achieve improved bounds for proximity problems including snowflake embeddings and clustering.

The traveling salesman problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem an algorithm that for any fixed $\varepsilon>0$ computes in randomized polynomial time a $(1+\varepsilon)$-approximation to the optimal tour in TSP instances that form an arbitrary metric space with bounded intrinsic dimension. The celebrated results of Arora [J. ACM, 45 (1998), pp. 753--782] and Mitchell [SIAM J. Comput., 28 (1999), pp. 1298--1309] prove that the above result holds in the special case of TSP in a fixed-dimensional Euclidean space. Thus, our algorithm demonstrates that the algorithmic tractability of metric TSP depends on the dimensionality of the space and not on its specific geometry. This result resolves a problem that has been open since the quasi-polynomial time algorithm of Talwar [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 281--290].

It has long been known that d-dimensional Euclidean point sets admit (1+ε)-stretch spanners with lightness WE= ε-O(d), that is the total edge weight is at most WE times the weight of the minimum spanning tree of the set [DHN93]. Whether or not a similar result holds for metric spaces with low doubling dimension has remained an open problem. In this paper, we resolve the question in the affirmative, and show that doubling spaces admit(1 + ε)-stretch spanners with lightness WD = (ddim /ε)O(ddim).

A major open problem in the field of metric embedding is the existence of dimension reduction for $n$-point subsets of Euclidean space, such that both distortion and dimension depend only on the doubling constant of the point set, and not on its cardinality. In this paper, we negate this possibility for $\ell_p$ spaces with $p>2$. In particular, we introduce an $n$-point subset of $\ell_p$ with doubling constant $O(1)$, and demonstrate that any embedding of the set into $\ell_p^d$ with distortion $D$ must have $D\ge\Omega((\frac{\log n}{d})^{\frac{1}{2}-\frac{1}{p}})$.

A major open problem in the field of metric embedding is the existence of dimension reduction for n-point subsets of Euclidean space, such that both distortion and dimension depend only on the doubling constant of the pointset, and not on its cardinality. In this paper, we negate this possibility for ℓp spaces with p > 2. In particular, we introduce an n-point subset of ℓp with doubling constant O(1), and demonstrate that any embedding of the set into ℓdp with distortion D must have D ≥ Ω ((c log n/d)1/2−1/p).

A classic result in the study of spanners is the existence of light low-stretch spanners for Euclidean spaces. These spanners have arbitrary low stretch, and weight only a constant factor greater than that of the minimum spanning tree of the points (with dependence on the stretch and Euclidean dimension). A central open problem in this field asks whether other spaces admit low weight spanners as well -- for example metric space with low intrinsic dimension -- yet only a handful of results of this type are known.

Recent advances in large-margin classification of data residing in general metric spaces (rather than Hilbert spaces) enable classification under various natural metrics, such as string edit and earthmover distance. A general framework developed for this purpose left open the questions of computational efficiency and of providing direct bounds on generalization error. We design a new algorithm for classification in general metric spaces, whose runtime and accuracy depend on the doubling dimension of the data points, and can thus achieve superior classification performance in many common scenarios. The algorithmic core of our approach is an approximate (rather than exact) solution to the classical problems of Lipschitz extension and of nearest neighbor search. The algorithm's generalization performance is guaranteed via the fat-shattering dimension of Lipschitz classifiers, and we present experimental evidence of its superiority to some common kernel methods. As a by-product, we offer a new perspective on the nearest neighbor classifier, which yields significantly sharper risk asymptotics than the classic analysis.

The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. The special case of TSP in bounded-dimensional Euclidean spaces has been a particular focus of research: The celebrated results of Arora [Aro98] and Mitchell [Mit99] - along with subsequent improvements of Rao and Smith [RS98] - demonstrated a polynomial time approximation scheme for this problem, ultimately achieving a runtime of Od,ε(n log n). In this paper, we present a linear time approximation scheme for Euclidean TSP, with runtime Od,ε(n). This improvement resolves a 15 year old conjecture of Rao and Smith, and matches for Euclidean spaces the bound known for a broad class of planar graphs [Kle08].

We introduce a new problem in the study of doubling spaces: Given a point set $S$ and a target dimension $d^*$, remove from $S$ the fewest number of points so that the remaining set has doubling dimension at most $d^*$. We present a bicriteria approximation for this problem and extend this algorithm to solve a group of proximity problems.

The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1+µ)-approximation to the optimal tour, for any fixed µ>0, in TSP instances that form an arbitrary metric space with bounded intrinsic dimension.

We present an approximate distance oracle for a point set S with n points and doubling dimension Λ. For every ε > 0, the oracle supports (1 + ε)-approximate distance queries in (universal) constant time, occupies space [ε−O(Λ) + 2O(Λ log Λ)]n, and can be constructed in [2O(Λ) log3 n + ε−O(Λ) + 2O(Λ log Λ)]n expected time. This improves upon the best previously known constructions, presented by Har-Peled and Mendel [13]. Furthermore, the oracle can be made fully dynamic with expected O(1) query time and only 2O(Λ) log n + ε−O(Λ) + 2O(Λ log Λ) update time. This is the first fully dynamic (1 + ε)-distance oracle.

The ℓ2 flattening lemma of Johnson and Lindenstrauss [JL84] is a powerful tool for dimension reduction. It has been conjectured that the target dimension bounds can be refined and bounded in terms of the intrinsic dimensionality of the data set (for example, the doubling dimension). One such problem was proposed by Lang and Plaut [LP01] (see also [GKL03, Mat02, ABN08, CGT10]), and is still open. We prove another result in this line of work: The snowflake metric d1/2 of a doubling set S ⊂ ℓ2 can be embedded with arbitrarily low distortion into ℓD2, for dimension D that depends solely on the doubling constant of the metric. In fact, the target dimension is polylogarithmic in the doubling constant. Our techniques are robust and extend to the more difficult spaces ℓ1 and ℓ∞, although the dimension bounds here are quantitatively inferior than those for ℓ2.

We present a new data structure that facilitates approximate nearest neighbor searches on a dynamic set of points in a metric space that has a bounded doubling dimension. Our data structure has linear size and supports insertions and deletions in O(log n) time, and finds a (1+ε)-approximate nearest neighbor in time O(log n) + (1/ε)O(1). The search and update times hide multiplicative factors that depend on the doubling dimension; the space does not. These performance times are independent of the aspect ratio (or spread) of the points.

This paper considers various flavors of the following online problem: preprocess a text or collection of strings, so that given a query string p, all matches of p with the text can be reported quickly. In this paper we consider matches in which a bounded number of mismatches are allowed, or in which a bounded number of "don't care" characters are allowed. The specific problems we look at are: indexing, in which there is a single text t, and we seek locations where p matches a substring of t; dictionary queries, in which a collection of strings is given upfront, and we seek those strings which match p in their entirety; and dictionary matching, in which a collection of strings is given upfront, and we seek those substrings of a (long) p which match an original string in its entirety. These are all instances of an all-to-all matching problem, for which we provide a single solution.The performance bounds all have a similar character. For example, for the indexing problem with n=|t| and m=|p|, the query time for k substitutions is O(m + (c1 log n)k⁄k! + # matches), with a data structure of size O(n (c2 log n)k⁄k!) and a preprocessing time of O(n (c2 log n)k⁄k!), where c1,c2 > 1 are constants. The deterministic preprocessing assumes a weakly nonuniform RAM model; this assumption is not needed if randomization is used in the preprocessing.