🤖 machine learning

Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$ -norms

This paper presents the first algorithm for online correlation clustering in the online-with-a-sample model that simultaneously achieves near-optimal competitive ratios for all $\ell_p$ -norms, effectively overcoming the fundamental hardness limitations of the standard random-order model.

Original authors: Sami Davies, Benjamin Moseley, Heather Newman

Published 2026-08-14

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Sami Davies, Benjamin Moseley, Heather Newman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the captain of a massive, chaotic ship, and your crew is made up of thousands of strangers. Your job is to sort them into smaller groups so everyone can work together. But here's the catch: some crew members get along famously (they are "positive" friends), while others hate each other's guts (they are "negative" enemies). If you put two enemies in the same group, they'll cause a fight. If you split two best friends into different groups, they'll be heartbroken. Your goal is to make the fewest mistakes possible. This is the heart of a problem computer scientists call correlation clustering.

Usually, we just want to minimize the total number of mistakes across the whole ship. But what if you care about fairness? What if you want to make sure no single crew member is stuck with a huge pile of enemies in their group, even if it means the total number of mistakes goes up slightly? This is the difference between looking at the "average" cost versus the "worst-case" cost for any single person. For a long time, computer scientists could solve this fairly well if they had the entire list of crew members in front of them at once. But what if the crew members arrive one by one, and you have to decide their group immediately, without knowing who is coming next? That's the online setting, and it's notoriously difficult. In fact, for the "fairness" version of the problem, it was thought to be almost impossible to do well without a crystal ball.

This paper tackles that exact nightmare scenario. The authors ask: Can we design a smart algorithm that sorts these arriving crew members into groups, ensuring that no one gets stuck with too many enemies, while also keeping the total number of fights low, all without knowing the future? The answer, surprisingly, is yes—but with a twist. The algorithm gets a tiny "sneak peek" at a random sample of the crew before the rest of them arrive. Using this small sample, the authors built a single algorithm that simultaneously achieves a near-perfect balance for every possible way of measuring fairness and total cost. They proved that this approach works with high probability, effectively bringing a powerful "offline" solution into the chaotic "online" world.

The Problem: The Great Sorting Chaos

Imagine you are running a massive party where guests keep walking through the door one by one. You have a list of who likes whom and who hates whom, but you can't see the future. As each guest arrives, you must instantly assign them to a table. If you put two enemies at the same table, they'll start an argument (a "disagreement"). If you put two best friends at different tables, they'll be sad (another "disagreement").

In the world of computer science, this is correlation clustering. The goal is to find a seating arrangement that minimizes these disagreements. For decades, researchers focused on minimizing the total number of disagreements. This is like counting every single argument and sad face in the room and trying to get that number as low as possible. This is called the $\ell_1$ -norm. It's efficient, but it can be unfair. You might end up with a seating chart where the total arguments are low, but one poor guest is sitting at a table with ten enemies, while everyone else is happy.

To fix this, scientists introduced the $\ell_\infty$ -norm (or $\ell_8$ -norm in the paper's notation, though it represents the maximum). This metric cares about the worst-off person. It asks: "What is the maximum number of enemies any single guest has to deal with?" The goal is to make that number as small as possible. This ensures fairness. But here's the rub: minimizing the total arguments and minimizing the worst-case argument are often at odds. You can't always have both.

The real challenge arises when you don't know the whole guest list in advance. In the online setting, guests arrive one by one, and you must seat them immediately. You can't wait to see who comes next to make a better decision. For a long time, researchers thought that in this "blind" online world, you could never do a good job at the fairness goal ( $\ell_\infty$ -norm). In fact, they proved that without any help, any algorithm would fail miserably, getting a score that is a huge fraction of the total number of guests ( $\Omega(n^{1/3})$ ). It seemed like a lost cause.

The Magic Trick: A Tiny Peek

The authors of this paper decided to try a different approach. Instead of being completely blind, they gave the algorithm a sample. Imagine that before the party starts, you are allowed to look at a small, random group of guests (say, 1% of them) and see who likes and hates whom. This is the Online-with-a-Sample (AOS) model.

The big question was: Is this tiny peek enough to break the "impossible" barrier? Can a small sample give the algorithm enough structural information to make smart decisions for the rest of the guests?

The answer is a resounding yes. The paper presents a single algorithm that uses this small sample to produce one seating chart that is simultaneously excellent for every way you might want to measure the party's success.

How the Algorithm Works: The "Pre-Clustering" and "Pivot" Dance

The algorithm is a clever two-step dance that happens as guests arrive.

Step 1: The Pre-Clustering Phase (The VIP Treatment)
When a new guest arrives, the algorithm checks the "sneak peek" sample.

The Check: Does this new guest have any friends in the sample? And are they close to any of the "VIP" tables (centers) identified in the sample?
The Decision: If the answer is yes, the guest is immediately assigned to the VIP table they are closest to. This is like saying, "You look like you fit in with this group we already know about."
The Safety Net: If the guest has no friends in the sample, or if they are too far from any VIP table, they don't get a seat yet. They are sent to a waiting area for the second phase.

Step 2: The Pivot Phase (The Last-Minute Shuffle)
The guests who didn't get a seat in the first phase are handled by a modified version of a classic strategy called the Pivot algorithm.

The Classic Pivot: Usually, this algorithm picks a guest at random and puts all their friends at their table.
The Twist: The authors modified this. If a guest is in the waiting area, the algorithm looks at their friends. But it only groups them with friends who are close according to the "distance" calculated from the sample. If a friend is too far away (based on the sample's data), they don't get grouped together, even if they are friends. This prevents the algorithm from making huge, clumsy mistakes based on bad guesses.

The Results: A Win for Everyone

The paper proves that this single algorithm is a miracle worker. It doesn't just solve the problem for one specific goal; it solves it for all goals at once.

Fairness ( $\ell_\infty$ -norm): The algorithm ensures that no guest is stuck with too many enemies. The "worst-case" number of enemies is only a small factor (related to $1/\epsilon^6$ and $\log n$ ) worse than the absolute best possible arrangement. This is a massive improvement over the previous belief that it was impossible to do better than a huge fraction of the total guests.
Total Efficiency ( $\ell_1$ -norm): It also keeps the total number of arguments low. On average, the total mistakes are only a small factor ( $O(1/\epsilon^6)$ ) worse than the best possible total.
The "All-Norms" Guarantee: The most exciting part is that it works for every measure in between. Whether you care about the average, the worst-case, or any balance in between, this single seating chart is nearly optimal for all of them simultaneously.

The authors also proved that their results are nearly the best possible. They showed that you need that small sample size ( $\epsilon$ ) to get these results; if you try to do it without a sample, or with a sample that is too small, the algorithm will fail. They also proved that in the standard "random order" model (where guests arrive in a random sequence but without a sample), the fairness problem is still impossible to solve well. This highlights that the "sneak peek" sample is the secret sauce that makes the difference.

Why This Matters

This paper is a breakthrough because it takes a problem that was thought to be unsolvable in a chaotic, real-time environment and solves it by using a tiny bit of historical data. It shows that even a small amount of "prior knowledge" (the sample) can completely change the rules of the game, allowing us to be both efficient and fair.

The authors didn't just find a way to seat guests; they found a way to balance global efficiency with individual fairness in a world where you can't see the future. They proved that with a little help from the past, we can make near-perfect decisions in the present, for everyone, all at once. This is the first time such a powerful "all-norms" guarantee has been achieved in the online setting, translating a theoretical dream into a practical reality.

Technical Summary: Online Correlation Clustering: Simultaneously Optimizing All $\ell_p$ -Norms

Problem Definition

The paper addresses Correlation Clustering in an online setting. In this problem, a complete graph $G=(V, E)$ is given where edges are labeled as positive (similarity) or negative (dissimilarity). The goal is to partition vertices into clusters to minimize disagreements: positive edges between different clusters and negative edges within the same cluster.

The objective is to minimize the $\ell_p$ -norm of the disagreement vector, where the $i$ -th coordinate represents the number of disagreements incident to node $i$ .

$\ell_1$ -norm: Minimizes the total number of disagreements (global efficiency).
$\ell_\infty$ -norm: Minimizes the maximum number of disagreements for any single node (individual fairness).
$\ell_p$ -norm ( $1 < p < \infty$ ): Interpolates between these two extremes.

The setting is the Online-with-a-Sample (AOS) model. An adversary fixes the input instance, but the algorithm is provided upfront with a random sample $S$ of $\epsilon n$ nodes (and their induced subgraph). The remaining nodes arrive sequentially in adversarial order and must be irrevocably assigned to a cluster.

Motivation and Hardness

Prior work established that in the standard purely online model (adversarial order), no sublinear competitive ratio is possible for any $\ell_p$ -norm. In the Random-Order (RO) model, while the $\ell_1$ -norm admits an $O(1)$ -competitive algorithm (via the Pivot algorithm), the authors prove a fundamental separation: any algorithm for the $\ell_\infty$ -norm in the RO model must have a competitive ratio of $\Omega(n^{1/3})$ .

This hardness result motivates the use of the AOS model. The paper asks whether a small random sample can provide sufficient structural information to break the online hardness barrier for $\ell_\infty$ -norm clustering and, more ambitiously, whether a single clustering can simultaneously approximate all $\ell_p$ -norms (the "all-norms" objective) in this online setting.

Methodology

1. Estimating Metrics via Sampling

The core challenge is adapting the offline "all-norms" algorithm (Davies, Moseley, and Newman [23]) to the online setting. The offline algorithm relies on a correlation metric $d$ and an adjusted correlation metric $d^*$ , which are combinatorial surrogates for the optimal solution to a convex relaxation.

Since the full graph is not available online, the authors estimate these metrics using the sample $S$ :

Subsampling: To avoid correlation issues between estimates, the sample $S$ is split into four independent subsamples: $S_d$ (distance), $S_p$ (pre-clustering centers), $S_b$ (counting), and $S_r$ (rounding).
Estimated Metrics:
- $\bar{d}$ : The correlation metric computed on the subgraph induced by $S_d$ .
- $\tilde{d}$ : The adjusted correlation metric computed using $\bar{d}$ and the rounding sample $S_r$ .
Properties: The authors prove that $\bar{d}$ is a 1-semi-metric and $\tilde{d}$ is a $(10/7)$ -semi-metric. Crucially, they show that the fractional cost of $\tilde{d}$ with respect to the optimal $\ell_p$ -norm cost ( $OPT_p$ ) is bounded, even though $\tilde{d}$ is only an estimate.

2. Algorithm Structure (Algorithm 1)

The proposed algorithm operates in two main phases:

Phase 1: Pre-clustering

Centers are selected from the sample $S_p$ and ordered by their estimated "density" (ball size) computed using $S_b$ .
When a node $v$ $v$ arrives:
- If $v$ has positive neighbors in $S_d$ (making it "eligible") and is close (within distance $c \cdot r$ in $\tilde{d}$ ) to an existing center, it is assigned to the earliest such center.
- If $v$ fails these checks, it is passed to Phase 2.

Phase 2: Pivot Phase

Nodes that were not pre-clustered are handled using variations of the Pivot algorithm.
Ineligible Nodes ( $V \setminus V_0$ ): Nodes with no positive neighbors in $S_d$ are clustered using the standard Pivot algorithm on the induced subgraph of ineligible nodes.
Eligible but Distant Nodes ( $V_0^1$ ): Nodes with positive neighbors in $S_d$ but far from all centers are clustered using a Modified Pivot algorithm. This version restricts pivots to only grab positive neighbors that are "close" according to the estimated metric $\tilde{d}$ .

3. Analysis Technique

The analysis relies on a "good event" ( $B_c$ ) where concentration inequalities ensure that estimates based on the sample are accurate. The cost analysis partitions disagreements into:

Pre-clustering phase: Disagreements are charged to the fractional cost of the estimated metric $\tilde{d}$ .
Pivot phase: Disagreements are charged to "bad triangles" (triples with two positive and one negative edge) and mapped to the optimal solution's disagreements.
Cross-phase: Disagreements between nodes clustered in different phases are bounded by relating them to the fractional costs of the metrics.

Key Contributions and Results

Theoretical Guarantees

The paper presents an algorithm that produces a single clustering with the following competitive ratios in the AOS model:

$\ell_\infty$ -norm (Fairness): $O(\frac{1}{\epsilon^6} \log n)$ -competitive with high probability.
$\ell_p$ -norms ( $1 < p < \infty$ ): $O(\frac{1}{\epsilon^8} \log^4 n)$ -competitive with high probability.
$\ell_1$ -norm (Global Efficiency): $O(\frac{1}{\epsilon^6})$ -competitive in expectation.

These results successfully translate the offline "all-norms" guarantee to the online world, achieving simultaneous approximation for all $p \in [1, \infty]$ .

Lower Bounds

The authors complement their upper bounds with nearly tight lower bounds for the AOS model:

$\ell_\infty$ -norm: Any randomized algorithm is $\Omega(\frac{1}{\epsilon} \log n)$ -competitive.
$\ell_1$ -norm: Any randomized algorithm is $\Omega(\frac{1}{\epsilon})$ -competitive.
RO Model Hardness: They prove that for $\ell_\infty$ -norm correlation clustering, any algorithm in the Random-Order model is $\Omega(n^{1/3})$ -competitive, establishing a strict separation between the $\ell_1$ and $\ell_\infty$ objectives in the RO setting.

Significance

The paper claims to provide the first affirmative answer to whether the powerful "all-norms" guarantee can be achieved in an online setting. Its significance lies in:

Overcoming Hardness: Demonstrating that the AOS model is strictly stronger than the RO model for fairness-promoting objectives like $\ell_\infty$ , where RO fails with polynomial lower bounds.
Robustness of Metrics: Showing that combinatorial metrics (correlation and adjusted correlation), typically requiring global knowledge, can be effectively estimated via sampling to guide near-optimal online decisions.
Generalizability: The technique of using independent subsamples to estimate different quantities and charging costs to these estimates offers a potential framework for other online problems with strong worst-case lower bounds.

The work successfully bridges the gap between offline all-norms optimization and online decision-making, proving that limited, well-distributed historical data (the sample) is sufficient to achieve fairness without sacrificing global efficiency.