On Mergable Coresets for Polytope Distance

Benwei Shi, Aditya Bhaskara, Wai Ming Tai, Jeff M. PhillipsarXiv 2023 · OpenReview

Abstract

We show that a constant-size constant-error coreset for polytope distance is simple to maintain under merges of coresets. However, increasing the size cannot improve the error bound significantly beyond that constant.

Introduction

In machine learning, finding the max-margin linear separator is a fundamental task, particularly for Support Vector Machines (SVMs). This task is mathematically equivalent to the polytope distance problem: finding the point in the convex hull of a set of points (a "polytope") that is closest to the origin.

As datasets scale beyond the memory capacity of a single machine, researchers rely on coresets. These are small subsets of data that serve as proxies for the full set, preserving its geometric properties within an error margin $\epsilon$. For streaming or distributed environments, these coresets must be mergeable: combining coresets from two different datasets should yield a valid coreset for the union of those datasets without a significant increase in error.

The Polytope Distance Problem

The core challenge is to approximate the distance from the origin to the convex hull of a point set $P$, denoted as $\text{conv}(P)$.

The geometry of the polytope distance problem.

This paper investigates whether $\epsilon$-coresets for this problem can be effectively merged. The authors' findings provide a theoretical "reality check," demonstrating that merging these coresets inevitably leads to a significant "error floor" determined by the data's geometry.

Geometric Constraints: Angular Diameter

The authors introduce a geometric parameter called angular diameter ($\theta$), defined as the maximum angle between any two vectors in the point set. Unlike previous metrics like "excentricity," angular diameter allows for the construction of minimal counter-examples that reveal the fundamental limits of merged coresets.

A simple baseline for this problem is to select the single point in the dataset closest to the origin. The authors show this point alone constitutes a coreset with an error of $(1 - \cos \theta)$. While easy to maintain, this error is fixed and does not improve as more points are added to the coreset.

Key Results: The Hardness of Merging

The paper presents three main theorems that outline the limitations of the "merge-and-reduce" strategy for polytope distance:

  1. Theorem 1: The closest point in a set $P$ is a $(1 - \cos \theta)$-coreset.
  2. Theorem 2: Merging two coresets, even if they individually have small errors, results in a merged coreset that cannot reliably beat the $(1 - \cos \theta)$ baseline. Increasing coreset size does not necessarily overcome this geometric error floor.
  3. Theorem 3: Even when starting with zero-error coresets (perfect summaries), the act of merging them introduces a significant error bound of $\frac{1 - \cos \theta}{1 + \cos \theta}$.
Merging two zero-error coresets results in a non-zero error bound.

These results suggest a fundamental connection to the hardness of finding the Minimum Enclosing Ball (MEB) in a streaming fashion, as polytope distance inherits similar "streaming-unfriendly" characteristics.

Conclusion and Implications

The primary takeaway is that the standard "merge-and-reduce" approach cannot maintain an arbitrarily small error $\epsilon$ for polytope distance. This has significant implications for building high-precision streaming algorithms for SVMs.

Future research may explore alternative definitions of coresets or approximations that allow for better mergeability, or investigate specific data distributions where the angular diameter is naturally small enough to mitigate these theoretical bounds.

Summary updated

Abstract

We show that a constant-size constant-error coreset for polytope distance is simple to maintain under merges of coresets. However, increasing the size cannot improve the error bound significantly beyond that constant.
BibTeX
@misc{shi2023mergable,
  author = {Benwei Shi and Aditya Bhaskara and Wai Ming Tai and Jeff M. Phillips},
  title = {{On Mergable Coresets for Polytope Distance}},
  year = {2023},
  eprint = {2311.05651},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2311.05651},
}
Figure