SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2302.10359 · NeurIPS · 2023

Replicable Clustering *

Amin Karbasi, Vahab Mirrokni, Hossein Esfandiari, Grigoris Velegkas, Felix Zhou

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

We design replicable algorithms in the context of statistical clustering under the recently introduced notion of replicability from Impagliazzo et al. [2022]. According to this definition, a clustering algorithm is replicable if, with high probability, its output induces the exact same partition of the sample space after two executions on different inputs drawn from the same distribution, when its internal randomness is shared across the executions. We propose such algorithms for the statistical k-medians, statistical k-means, and statistical k-centers problems by utilizing approximation routines for their combinatorial counterparts in a black-box manner. In particular, we demonstrate a replicable O(1)-approximation algorithm for statistical Euclidean k-medians (k-means) with Õ(poly(k, d)k log log k ) sample complexity. We also describe an O(1)-approximation algorithm with an additional O(1)-additive error for statistical Euclidean k-centers, albeit with Õ(poly(k) exp(d)) sample complexity. In addition, we provide experiments on synthetic distributions in 2D using the k-means++ implementation from sklearn as a black-box that validate our theoretical results 2 . * Authors are listed alphabetically. 2 https://anonymous.4open.science/r/replicable_clustering_experiments-E380 37th Conference on Neural Information Processing Systems (NeurIPS 2023).

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2302.10359")
get_code_for_paper("2302.10359")
have("2302.10359")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2302.10359.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2302.10359.svg)](https://syntology.ai/paper/2302.10359)

Connect an agent — have() is free.