PaperlayerView exact revision on arXiv

Source-linked AI summary

Consistent k-Clustering for General Metrics

Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson

arXiv:2011.06888v1cs.DS

TL;DR

The paper asks whether an insertion-stream clustering can remain a constant-factor approximation while changing centers only a near-minimal number of times. It introduces robust centers and structural lemmas for consistent k-median, achieving k·polylog(n, Δ) changes, matching the offline guarantee up to polylogarithmic factors.

  • Problem

    Consistent k-median seeks constant-factor clustering throughout an insertion stream while minimizing center changes, closing the gap between prior online and offline guarantees.

  • Method

    The algorithm combines Meyerson’s sketch with robust centers and structural lemmas that support few swaps under weighted insertions.

  • Results

    The algorithm maintains a constant-factor approximation using k·polylog(n, Δ) center changes, matching the offline setting up to polylogarithmic factors.

  • Takeaways & Limitations

    Knowing future insertions is not key for achieving the offline-scale number of center changes in consistent k-median.

  • Takeaways & Limitations

    The exposition assumes n and Δ are known in advance, although restarting when either grows by a constant factor removes this requirement with additional losses.

Abstract

from arXiv · show

Given a stream of points in a metric space, is it possible to maintain a constant approximate clustering by changing the cluster centers only a small number of times during the entire execution of the algorithm? This question received attention in recent years in the machine learning literature and, before our work, the best known algorithm performs $\widetilde{O}(k^2)$ center swaps (the $\widetilde{O}(\cdot)$ notation hides polylogarithmic factors in the number of points $n$ and the aspect ratio $Δ$ of the input instance). This is a quadratic increase compared to the offline case -- the whole stream is known in advance and one is interested in keeping a constant approximation at any point in time -- for which $\widetilde{O}(k)$ swaps are known to be sufficient and simple examples show that $Ω(k \log(n Δ))$ swaps are necessary. We close this gap by developing an algorithm that, perhaps surprisingly, matches the guarantees in the offline setting. Specifically, we show how to maintain a constant-factor approximation for the $k$-median problem by performing an optimal (up to polylogarithimic factors) number $\widetilde{O}(k)$ of center swaps. To obtain our result we leverage new structural properties of $k$-median clustering that may be of independent interest.

1. Introduction

The paper studies consistent k-median clustering for insertion streams, seeking constant-factor solutions while limiting center changes. It closes the gap between prior online and offline guarantees with a k·polylog(n, Δ)-change algorithm.

  • 1. Introduction: The consistent k-median problem maintains a constant-factor approximation for an evolving insertion stream while minimizing changes to consecutive center sets.Consistency matters because changing centers can trigger costly recomputations in downstream applications.
  • 1. Introduction: Prior work used at most k^2·polylog(n, Δ) changes online, while offline knowledge permits k·polylog(n, Δ) changes and requires Ω(k log(n Δ)) in simple instances.The prior online algorithm compresses the stream with Meyerson’s sketch and then recomputes solutions on weighted insertions.
  • 1. Introduction: The paper closes this gap with the first consistent k-median algorithm achieving a constant-factor approximation using k·polylog(n, Δ) center changes.This matches the offline change bound up to polylogarithmic factors without knowledge of future insertions.
  • 1. Introduction: The approach introduces robust centers and new structural properties that limit updates even under adversarial point insertions.It applies Meyerson’s sketch and reduces the average changes per weighted insertion from k·polylog(n, Δ) to polylog(n, Δ).
  • 1. Introduction: The consistency notion is closely related to recourse, where online algorithms limit changes to maintain approximate combinatorial solutions.The paper also notes extensions beyond k-median to constant-p norm objectives and related geometric settings.

2. Overview of Our Approach

The algorithm combines phase-based cost stabilization, sketching, and robust-center structural lemmas. These components reduce center changes while preserving constant-factor clustering quality under weighted insertions.

  • 2. Overview of Our Approach: The stream is divided into log(nΔ) phases so the optimal cost remains within controlled multiplicative bounds during each phase.A phase ends when an approximate current cost increases by a factor of six, implying a bounded increase in the optimum.
  • 2. Overview of Our Approach: Meyerson’s sketch reduces the stream to k·polylog(n, Δ) weighted points, transferring an average C changes per weighted insertion into Ck·polylog(n, Δ) total changes.This sketching step preserves a constant-factor approximation while exposing the main opportunity for reducing updates.
  • 2. Overview of Our Approach: When centers can be paired with nearby, well-separated optimum centers, future insertions mainly decompose into disjoint 1-median problems.Complex instances require handling only a subset of such well-separated pairs.
  • 2. Overview of Our Approach: If the current solution has k−ℓ well-separated pairs, a constant-factor solution can use Ω(ℓ) fewer centers through a carefully constructed fractional solution.Centers outside well-separated pairs can be charged to nearby centers because they lie close to multiple optimum centers.
  • 2. Overview of Our Approach: After reducing centers, the algorithm opens arriving points and later performs O(ℓ+1) swaps to restore a constant-factor solution and robustify its centers.EpochAlgorithm first removes centers, handles ℓ′ insertions, then uses LP-based swaps and robustification.

3. Preliminaries and Formal Statement of the Main Result

The paper formalizes consistent k-median on insertion streams as maintaining a constant approximation while minimizing changes to center sets. Its main theorem guarantees constant approximation and k·polylog(n, Δ) changes with high probability.

  • 3. Preliminaries and Formal Statement of the Main Result: Consistent k-median receives points by insertion and seeks a constant-factor solution at every time while minimizing cumulative changes to consecutive center sets.The algorithm need not know future points, although the exposition initially assumes n and Δ are known.
  • 3. Preliminaries and Formal Statement of the Main Result: The k-median objective chooses at most k centers minimizing the sum of distances from points to their nearest center.For weighted inputs, each point’s distance contribution is multiplied by its weight.
  • 3. Preliminaries and Formal Statement of the Main Result: The algorithm’s stability objective counts how often the maintained center set changes during the entire execution.This formalizes consistency as a cumulative measure of center-set modifications.
  • 3. Preliminaries and Formal Statement of the Main Result: Theorem 3.1 provides center sets after every insertion that induce a constant-approximation clustering with probability at least 1−1/n^8.The theorem applies simultaneously across all prefixes of the insertion stream.
  • 3. Preliminaries and Formal Statement of the Main Result: The total number of changes in consecutive center sets is at most k·polylog(nΔ), matching the lower bound up to polylogarithmic factors.This is the paper’s formal consistency guarantee.

4. Robust Centers

Robust centers are chosen to remain useful as cluster structure changes across exponentially growing distance scales. The resulting robust tuples provide centers that can tolerate insertions and evolving cluster boundaries while limiting future center changes.

  • Motivation: Robust centers are designed for clusters whose structure may grow, shrink, merge, or split after further insertions.They favor stability under uncertain future changes rather than only minimizing the current clustering cost.
  • Intuition: Figure 1 illustrates that a robust initial center may require only one added center after a cluster splits, whereas a non-robust choice requires changing two centers.The second panel shows robust tuples retaining a point when an inner ball has large average cost and optimizing within it when average cost is small.
  • Construction: The construction recursively selects points across exponentially growing balls, either retaining a point when average cost is large or choosing a low-cost center inside the ball.This prevents movement when points lie near a ball boundary and indicate weak concentration around the current center.
  • Structural properties: The first point p_0 is an approximately good center for any superset containing the relevant ball around p_i.Lemma 4.5 establishes this bounded-cost property for subsets P′ that contain Ball(p_i, 10^i).
  • Structural properties: A t-robust tuple has nested balls and keeps its first center within distance 10^j/2 of every later tuple point.For each j, dist(p_j−1, p_j) ≤ 10^j/2 and Ball(p_j−1, 10^j−1) is contained in Ball(p_j, 10^j).

5. Description of EpochAlgorithm

EpochAlgorithm maintains bounded-robust solutions over a compressed stream by removing unnecessary centers, handling insertions, swapping centers, and robustifying the result. These steps preserve constant approximation while preparing the next epoch for further insertions.

  • Epoch structure: The stream is compressed into eO(k) weighted insertions, and the compressed stream is processed through successive epochs.Each epoch receives the previous epoch’s final bounded-robust clustering as its starting solution.
  • Initialization: EpochAlgorithm begins with a bounded-robust solution that is 100-approximate and whose centers satisfy scale-dependent robustness conditions.The initial solution is obtained from a constant-factor approximation and then robustified.
  • Robustification: Robustify replaces non-robust centers using MakeRobust and increases clustering cost by only a factor 3/2 before the next epoch.MakeRobust is called at most once for each center, so the robustification procedure terminates.
  • Epoch steps: It removes ℓ centers while increasing cost by at most a constant factor, creating capacity to open the next ℓ inserted points without increasing cost.The preprocessing obtains a solution with at most k−ℓ centers before handling insertions.
  • Epoch steps: After one additional insertion, an LP-rounding step performs O(ℓ+1) swaps and produces a 13-approximate intermediate solution with high probability.The procedure swaps 4ℓ′ elements for ℓ′ = 5ℓ+5 and compares against an optimum using at most ℓ′ swaps.

6. Bound on the Number of Changes

The consistency analysis bounds center changes by organizing centers into chains and controlling new, invalidated, and robustness-increasing centers. This yields a polylogarithmic bound in the compressed stream size and aspect ratio.

  • Robustification accounting: Robustify calls MakeRobust at most once for each center, and a replaced center is never robustified again.This termination property supports the chain-based accounting of center changes.
  • Main bound: The maintained solution changes at most O(m(log ∆)^2) times, where m=eO(k) is the number of weighted insertions in the compressed stream.The bound follows by counting new and updated centers across epochs.
  • Chain decomposition: Centers form chains in which each successor replaces its parent through MakeRobust, while chain starts are new centers.The total number of chains, equivalently new centers, is at most 20m.
  • Invalidation control: A robust center remains robust after insertions whenever no new point enters its radius-2·10^t neighborhood.This condition identifies which insertions can invalidate a center’s robustness.
  • Chain decomposition: At most O(m log ∆) updated centers are invalidated by inserted points, while robustness increases for at most O(log ∆) times the number of new centers plus invalidated updates.These bounds control the total length of the center chains.

7. Cost Analysis of EpochAlgorithm

EpochAlgorithm exploits well-separated pairs to remove centers while controlling cost, then robustifies the resulting clustering to maintain bounded approximation across an epoch.

  • Cost Analysis of EpochAlgorithm: EpochAlgorithm produces center sets U(1), ..., U(ℓ+1) for the successive point sets P(1), ..., P(ℓ+1).
  • Cost Analysis of EpochAlgorithm: The algorithm preserves constant-factor approximation for intermediate point sets and makes the final set U(ℓ+1) a bounded-robust solution.The intermediate clustering is (6 · 100 · c)-approximate, while the final solution is established as 100-approximate before invoking bounded robustness.
  • Cost Analysis of EpochAlgorithm: Well-separated pairs isolate matched centers in U and V, enabling the analysis to distinguish removable and non-removable centers.A pair satisfies both separation inequalities with γ = 2000.
  • Cost Analysis of EpochAlgorithm: Removing at least ⌊m/4⌋ centers is possible when k−m well-separated pairs exist, while keeping the resulting clustering's cost bounded.
  • Cost Analysis of EpochAlgorithm: Step 1 removes ℓ ≥ ⌊m/4⌋ centers, where m counts centers in U lacking a well-separated partner in V.
  • Cost Analysis of EpochAlgorithm: Fractional opening and assignment in the standard LP relaxation support the center-removal lemma, whose cost bound transfers to an integral clustering using integrality gap at most 3.

8. Consistent k-Clustering Algorithm and Analysis

The algorithm combines Multi-Meyerson's sketch with EpochAlgorithm, restarting when the optimum cost rises substantially. It maintains a constant approximation with k · polylog(n, ∆) total center changes.

  • Consistent k-Clustering Algorithm and Analysis: Multi-Meyerson's sketch builds an on-the-fly weighted instance of size k · polylog(n, ∆) whose approximate solutions transfer to the original stream.The weighted points have positive integer weights summing to at most 2n.
  • Consistent k-Clustering Algorithm and Analysis: The algorithm restarts Multi-Meyerson when an approximate solution cost increases by a factor of 6, yielding at most log(n∆) restarts.Each restart corresponds to an optimum-cost increase between factors 2 and 18.
  • Consistent k-Clustering Algorithm and Analysis: Each run initializes EpochAlgorithm with a robustified constant-approximate solution, and the output remains a constant approximation throughout the execution.
  • Consistent k-Clustering Algorithm and Analysis: The total changes combine at most k log(n∆) changes from run restarts with the polylogarithmic changes incurred inside EpochAlgorithm.
  • Consistent k-Clustering Algorithm and Analysis: Theorem 3.1 guarantees a constant-approximation clustering after every insertion with at most k · polylog(n∆) changes in consecutive center sets.
  • Consistent k-Clustering Algorithm and Analysis: If n and ∆ are unknown, restarting whenever either grows by a constant factor preserves the guarantee with additional constant approximation and polylogarithmic change factors.

9. LP-based Algorithm for Swapping and Removing Centers

The section develops LP-based procedures for swapping or removing centers while preserving constant-factor clustering quality under bounded changes. Rounding yields a high-probability swapping guarantee, while an LP-size argument supports center removal.

  • Swapping Centers: The swapping procedure finds centers differing in at most 4ℓ centers while achieving a factor-13 approximation to the best solution differing by at most ℓ centers.The guarantee holds with probability at least 1 − 1/(n+∆)^10.
  • Swapping Centers: The LP minimizes clustering cost while enforcing center-opening, point-assignment, at-most-k-center, and bounded-change constraints.The initial center set is encoded through y0, and the change budget is controlled by ℓ.
  • Swapping Centers: Rounding opens at most k centers with probabilities matching fractional variables and has expected cost at most 3.25 times the fractional solution.Markov bounds and repetition combine the desired properties into a high-probability guarantee.
  • Removing Centers: The removing-centers procedure searches over ℓ and returns a 3-approximate solution with at most k − ℓ centers and cost at most 3c times the current solution cost.The LP certifies that no solution with fewer than k − ℓ centers can achieve cost at most c times the current cost.

A. Multi-Meyerson Procedure

The Multi-Meyerson procedure converts an insertion stream into a weighted stream while preserving approximation quality and controlling total weight. Its guarantees hold with high probability throughout the stream.

  • Multi-Meyerson Procedure: The procedure is analyzed by first establishing expected guarantees, applying Markov’s inequality for constant probability, and repeating copies to boost success probability.The construction is explicitly designed to obtain stronger guarantees than earlier uses of similar techniques.
  • Multi-Meyerson Procedure: Multi-Meyerson produces a weighted initial solution and insertion stream that preserve the relevant instance structure with probability at least 1 − 1/(n+∆)^10.The resulting weights are positive integers with total sum at most 2n.
  • Multi-Meyerson Procedure: Any α-approximate solution for the weighted instance is also an O(α + 1)-approximate solution for the corresponding original prefix.This guarantee applies after each corresponding insertion in the original stream.

A.1. Meyerson’s Sketch

Meyerson’s sketch maintains a dynamic center set by opening arriving points probabilistically according to their distance from existing centers. Its analysis bounds both opening behavior and assignment cost using optimal-cluster partitions.

  • Meyerson’s Sketch: The analysis uses an optimum estimate GOPT and tracks the optimum value OPT_i after each insertion to relate the sketch’s guarantees to the evolving instance.The estimate is obtained using known k-median algorithms and is bounded relative to the relevant optimum values.
  • Meyerson’s Sketch: Upon insertion, the sketch opens a point with probability min{1, dist(x,S)/(k(log ∆ + 1)GOPT)} and otherwise assigns it to the nearest open center.The maintained solution starts empty, and dist(x,∅) is defined as infinity.
  • Meyerson’s Sketch: The analysis partitions each optimal cluster into distance scales, yielding k(log ∆ + 1) partitions for bounding opening and assignment costs.Within a partition, the expected cumulative opening contribution before the first center opens is controlled by the optimum estimate.
  • Meyerson’s Sketch: The sketch’s expected-cost analysis compares later assignments with the first opened point in each partition and bounds their distances using the triangle inequality.The same partition structure controls the cost of points inserted after a center opens.

A.2. Extending Meyerson’s Sketch to Multi-Meyerson

Multi-Meyerson amplifies Meyerson’s sketch by running logarithmically many copies and selecting copies with the needed properties. It then constructs a weighted stream whose insertions preserve those guarantees.

  • Extending Meyerson’s Sketch to Multi-Meyerson: Running q = O(log(n + ∆)) copies in parallel yields, with probability 1 − 1/(n+∆)^10, a copy satisfying the required properties at every relevant prefix.The high-probability statement follows from the individual-copy lemmas and repetition.
  • Extending Meyerson’s Sketch to Multi-Meyerson: The construction assumes the optimum remains within the stated growth condition, enabling the estimate GOPT to remain comparable to the initial and final optimum values.Adding points can decrease the optimal cost by at most a factor of 2, which supports the comparison used in the analysis.
  • Extending Meyerson’s Sketch to Multi-Meyerson: The sketch size is bounded with probability at least 3/4 by |S| ≤ 4βk, where β = (1 + 4 · 18)k(log ∆ + 1).This bound is obtained by applying Markov’s inequality to the underlying sketch estimates.
  • Extending Meyerson’s Sketch to Multi-Meyerson: The construction appends points to the weighted stream according to copy behavior, allowing points to appear multiple times with dynamically changing weights.Weights assigned at insertion cannot later change, so repeated insertions encode subsequent weight changes.

Multi-Meyerson Procedure.

The Multi-Meyerson Procedure constructs a bounded weighted stream from multiple Meyerson sketches and analyzes its clustering quality using assignment weights, approximation guarantees, and metric inequalities.

  • Multi-Meyerson Procedure: q Meyerson sketches contribute O(qk(log Δ+1)) weight-1 points because larger sketches are skipped.Each inserted point can be reinserted at most log n+1 times, further bounding the constructed stream length.
  • Multi-Meyerson Procedure: The procedure tracks assignment multiplicities through weights w(y) and aggregates them into current stream weights v(y).For any stream point y, its assignment count equals w(y); the analysis groups weights by powers of two.
  • Multi-Meyerson Procedure: With probability 1 − 1/(n+Δ)^10, one Meyerson sketch copy has both a good approximation ratio and size at most 292k(log Δ+1).That size bound ensures all points from the selected sketch copy remain in the stream, enabling comparison with the algorithm's centers.
  • Multi-Meyerson Procedure: The clustering-cost analysis combines triangle inequality, Lemma A.7, Eq. (25), and the α-approximation guarantee for U.It also compares arbitrary clustering costs with OPT(Pr), where Pr is the union of the output set P and current output stream σ.
Loading 2011.06888v1…