Research map / Learning theory and algorithms / Clustering

Relative Error Fair Clustering in the Weak-Strong Oracle Model

ICML 2025 · Learning theory and algorithms › Clustering · approach: Fair clustering approximation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first (1+eps)-coreset constructions for fair k-median (and general (k,z)-clustering without fairness) in the weak-strong oracle model using poly(k log n/eps) strong oracle queries, via heavy-hitter ring sampling with recursive peeling.

Problem

Fair k-median/k-clustering when distances come from a cheap but possibly adversarially inaccurate weak oracle and an expensive exact strong oracle; the goal is to minimize strong oracle queries while obtaining near-optimal fair clustering.

Approach

Uses heavy-hitter sampling to identify exact ring assignments only for sampled points (via strong queries), then recursively peels off points from light rings using weak-oracle distance estimates, building ring-based coresets that preserve fairness (assignment-preserving) with (1+eps) guarantees.

Key results

• Fair k-median coreset of size Otilde(Lambda k^2/eps^2) using Otilde(Lambda k) strong point queries, improving over prior constant-factor (>10) approximations in the weak-strong oracle model.
• Assignment-preserving coreset of size O(k^2 log^4 n log(n/eps)/eps^2) using O(k log^4 n) strong point queries.
• (k,z)-clustering coreset of size Otilde(k^2/eps^3) for general z=O(1) with Otilde(k^2/eps^3) strong oracle queries; experiments show outperforming uniform sampling baseline.

Limitations

• Fair-coreset size and query bounds carry higher polylog(n) and 1/eps factors than unconstrained case
• Obtaining the actual (1+eps)-approximate clustering may take exponential time, so post-processing approximation algorithms are needed
• Dependence on k is not optimal for (k,z)-clustering coresets

Experimental setup

Datasets: Adult Default of Credit Card Clients

Benchmarks: Adult Default of Credit Card Clients

Metrics: clustering cost (coreset quality)

Baselines: uniform sampling with re-weighting

Builds on: weak-strong oracle model (Bateni et al.) ring sampling (Chen) assignment-preserving coresets Meyerson sketch

Closest papers by meaning

• Proportional Fairness in Non-Centroid Clustering (NeurIPS 2024 · similarity 0.89)
• Parameterized Approximation Schemes for Fair-Range Clustering (NeurIPS 2024 · similarity 0.88)
• Towards Fairer Centroids in K-means Clustering (AAAI 2024 · similarity 0.88)
• Fair Clustering via Alignment (ICML 2025 · similarity 0.88)
• Fair Clustering in the Sliding Window Model (ICLR 2025 · similarity 0.88)
• Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems (ICLR 2025 · similarity 0.87)