PaperlayerView exact revision on arXiv

Source-linked AI summary

Streaming algorithms for robust max-min diversification

Andrea Pietracaprina, Geppino Pucci, Stefano Zanon

arXiv:2610.01456v1cs.LG

TL;DR

Max-min diversification is vulnerable to noisy points, and the prior coreset-based streaming approach has offline construction and may return fewer than k points. The paper presents a deterministic one-pass coreset algorithm that, under an inlier–outlier separation assumption, returns a (2 + ε)-approximate solution of k inliers.

  • Problem

    Max-min diversification is sensitive to noise, while the prior streaming approach requires offline linear-memory coreset construction and can return fewer than k points.

    Source: §1 · p. 2, §1.1 · pp. 3–4

  • Method

    A deterministic one-pass coreset algorithm identifies outliers by nearest-neighbor distances and runs a sequential algorithm on the remaining points under an inlier–outlier separation assumption.

    Source: §1.2 · p. 5, §2.1 · p. 6, §3 · p. 11

  • Results

    The algorithm returns k points with no outliers at a 2 + ε approximation, uses memory independent of n over wide parameter ranges, and has amortized update time proportional to coreset size on sufficiently long streams.

    Source: §1.2 · p. 5

  • Takeaways & Limitations

    For wide ranges of k, z, ε, and D, robust max-min selection can use memory independent of n, with amortized update time also independent of n for sufficiently long streams.

    Source: §1.2 · p. 5

    The criticized [4] streaming approach requires offline coreset construction with linear memory and may return fewer than k points.

    Source: §1.1 · pp. 3–4

Abstract

from arXiv · show

Given a set of $n$ points $X$ in a metric space and an integer $k$, max-min diversification aims to select $k$ points of $X$ maximizing their minimum pairwise distance. This objective function is however highly vulnerable to noisy points. In[Amagata, AAAI23], a robust formulation is proposed which addresses this vulnerability by excluding solutions containing any of $z$ outliers, defined as the $z$ points in $X$ with the largest nearest-neighbor distances. That paper also presents a coreset-based streaming algorithm for the new formulation, based on a suitable inlier-outlier separation assumption. However, we identify three shortcomings in the algorithm by [Amagata, AAAI23]: its coreset construction requires an offline computation over $X$, which needs memory linear in $n$, in stark contrast with the typical goals of stream processing; the one-pass procedure used to extract the solution from the coreset may return fewer than $k$ points (hence, an unfeasible solution) because it permanently discards points too far from the current solution; and its outlier-exclusion guarantee is only probabilistic and weakens as the coreset size shrinks. In contrast, we present a deterministic coreset-based algorithm that, under a natural inlier-outlier separation assumption (similar to the one used in [Amagata, AAAI23]), returns exactly $k$ inliers which are a $(2+\varepsilon)$-approximate solution, for any $\varepsilon>0$, thus only $\varepsilon$ above the best polynomial-time sequential approximation, even without outliers. Its one-pass streaming implementation adapts obliviously to the dataset's doubling dimension $D$ and, for wide ranges of $k$, $z$, $\varepsilon$, and $D$, it uses memory independent of $n$. For sufficiently long streams, its amortized update time is proportional to the coreset size, thus also independent of $n$.

1 Introduction

Max-min diversification selects k points to maximize their minimum pairwise distance, but distant noisy points can distort this objective. The paper critiques prior streaming methods and presents coreset-based sequential and streaming algorithms for robust diversification under an inlier–outlier separation assumption.

1 Introduction

  • Max-min diversification maximizes the minimum pairwise distance among k selected points, but distant noise can skew the objective and attract farthest-first selection.The robust formulation excludes the z points farthest from their respective nearest neighbors.Source: §1 · pp. 1–2
  • Coresets support small-memory stream processing by letting an expensive sequential algorithm run on a small subset, with quality often regulated by doubling dimension D.Source: §1 · p. 2

1.1 Previous work

  • Amagata proposed Greedy and Coreset approaches, but Coreset construction scans all of X offline and requires memory linear in n.Source: §1.1 · p. 3
  • The Coreset scan may permanently discard points and return fewer than k, while its no-outlier guarantee is probabilistic and weakens as the coreset shrinks.A constant success probability p requires |C| = z/(1 − p).Source: §1.1 · p. 4

1.2 Our contribution

  • Using distinct separation parameters α and β, rather than β = α as in, enables exact deterministic identification of outliers under a sharper separation assumption.The proposed sequential coreset has k(8/ε′)^D + z points and is a (1 + ε)-coreset.Source: §1.2 · p. 5
  • The deterministic one-pass algorithm returns k points with no outliers at approximation ratio 2 + ε, uses memory independent of n over wide parameter ranges, and adapts obliviously to D.For sufficiently long streams, amortized update time is proportional to the coreset size; the ratio is ε above the best polynomial-time ratio even without outliers.Source: §1.2 · p. 5

2 Preliminaries

The preliminaries define max-min diversification with outliers, introduce coresets and doubling dimension, and review the k-center tools used in the algorithms.

2 Preliminaries

  • The preliminaries set notation for the metric dataset and define d(x,Y) as the distance from x to its nearest point in Y.The dataset is X, with n points and distance function d.Source: §2 · p. 6

2.1 Problem definition

  • Max-min diversification selects k points maximizing their minimum pairwise distance; the outlier version excludes the z points with largest nearest-neighbor distances.The formulation addresses noisy points that can distort this distance-based objective.Source: §2.1 · p. 6

2.2 γ-Coreset

  • A γ-coreset contains at least k inliers and transfers a c-approximation on its inliers into a c·γ-approximation for the full problem.The stated transfer assumes the inliers can be retrieved from the coreset.Source: §2.2 · p. 7

2.3 Doubling Dimension

  • Doubling dimension D is the smallest value for which every radius-r ball can be covered by at most 2^D balls of radius r/2.This property bounds finer coverings as well.Source: §2.3 · p. 7

2.4 k-Center Problem

3 Coreset-based sequential algorithm

The section presents a simpler 2-approximation and CoresetMMD, which builds a more accurate coreset by extending GMM until the clustering radius is small. Under the stated separation assumption, the method gives a c(1+ε)-approximation, with linear time in a constant-parameter setting.

3 Coreset-based sequential algorithm

  • 2-approximation: the simpler GMM strategy identifies the z outliers among k+z selected points and returns the remaining k inliers.The guarantee follows under the stated separation assumption.Source: §3 · p. 10
  • CoresetMMD starts with k+z GMM points, identifies outliers by nearest-neighbor distances, then adds points until the clustering radius is O(εr).It runs the sequential algorithm on the coreset after removing the identified outliers.Source: §3 · p. 11
  • c(1+ε)-approximation: CoresetMMD returns this guarantee when its sequential algorithm is a c-approximation.With constant k, z, and doubling dimension, an exact sequential algorithm yields a (1+ε)-approximation in linear time.Source: §3 · pp. 11–12
  • The separation assumption lets the final coreset preserve inliers corresponding to the optimal solution, supporting its (1+ε)-coreset guarantee.The proof uses the fact that an optimal point's proxy cannot be an outlier.Source: §3 · p. 12

4 Streaming Algorithm

The algorithm builds a weighted coreset in one streaming pass, identifies and removes the outliers, then runs a sequential approximation algorithm on the remaining points. Under the stated separation assumption, it returns a λ(1+ε)-approximation and has working space independent of stream length when ε, δ, and D are constant.

4 Streaming Algorithm

  • The streaming coreset uses a scaling routine, adds sufficiently distant points, and periodically shrinks by merging nearby points and their weights.Shrinking occurs when the estimated radius r exceeds 2R; the processing order can affect the resulting coreset.Source: §4 · pp. 13–14
  • When α > β + ε′/2, the outliers are the z zero-weight coreset points with the largest nearest-neighbor distances.The algorithm removes them before applying the sequential solver to the remaining coreset points.Source: §4 · p. 16
  • For ε′ < 2α, the constructed set is a 1/(1−ε′)-coreset for max-min diversification with outliers.Source: §4 · p. 17
  • Under α > β + ε′/2, the one-pass algorithm returns a λ(1+ε)-approximation when its final sequential algorithm is a λ-approximation.The theorem sets ε′ = ε/(1+ε).Source: §4 · p. 17
  • With ε, δ, and D constant, working space and query time are linear in k+z and independent of stream size n.For reasonable aspect ratios, amortized update time can be considerably smaller than worst-case update time.Source: §4 · p. 18
Loading 2610.01456v1…