Symmetric Randomized Dependent Rounding

David G. Harris, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh

Abstract

Clustering problems are fundamental to unsupervised learning. There is an increased emphasis on fairness in machine learning and AI; one representative notion of fairness is that no single demographic group should be over-represented among the cluster-centers. This, and much more general clustering problems, can be formulated with "knapsack" and "partition" constraints. We develop new randomized algorithms targeting such problems, and study two in particular: multi-knapsack median and multi-knapsack center. Our rounding algorithms give new approximation and pseudo-approximation algorithms for these problems. One key technical tool, which may be of independent interest, is a new tail bound analogous to Feige (2006) for sums of random variables with unbounded variances. Such bounds can be useful in inferring properties of large networks using few samples.

Introduction

Clustering is a cornerstone of unsupervised machine learning, traditionally focused on minimizing the distance between data points and their assigned centers. However, as AI systems are increasingly deployed in sensitive domains like healthcare and urban planning, the need for "fair" clustering has become paramount. Fairness in this context often translates to ensuring that cluster centers are distributed equitably across different demographic groups.

Mathematically, these requirements are modeled as knapsack constraints (budgets on specific groups) and partition constraints. Solving these problems typically involves Linear Programming (LP) relaxations, which yield fractional solutions. The challenge lies in "rounding" these fractional values into discrete decisions (0 or 1) without violating the constraints or significantly degrading the clustering quality.

The Rounding Dilemma: Independence vs. Correlation

Standard rounding techniques face a fundamental trade-off. Independent rounding preserves the statistical independence of variables—which is crucial for maintaining clustering quality—but frequently violates hard budget constraints. Conversely, traditional dependent rounding strictly enforces constraints but introduces high correlations between variables. Because clustering performance depends on the joint behavior of multiple potential centers, these correlations often destroy the mathematical guarantees of the solution.

This paper introduces a novel algorithmic framework, Knapsack-Partition Rounding (KPR), designed to navigate this tension by combining the strengths of both dependent and independent rounding.

The Knapsack-Partition Rounding (KPR) Framework

The KPR algorithm operates through a three-step technical process:

  1. Early-Stopping Random Walk: Instead of rounding every variable to 0 or 1, KPR performs a random walk within the constraint space and stops while a small, constant number of fractional entries remain. This "early stopping" prevents the variables from becoming overly correlated.
  2. Additive Pseudo-Approximation: To resolve the remaining fractional variables, the algorithm employs independent rounding. While this may lead to a slight violation of the knapsack constraints, the authors prove that the violation is additive (e.g., exceeding a budget by a fixed number of items $q$) rather than multiplicative (e.g., exceeding a budget by a percentage). In fairness applications, an additive violation of 1 or 2 units is often far more acceptable than a percentage-based overflow.
  3. A New Concentration Inequality: To validate these additive bounds, the authors developed a new "Samuels-Feige" type tail bound for sums of negatively associated random variables. Remarkably, this bound does not depend on the variance of the variables, making it a robust tool for handling unbounded random variables.

Key Results and Applications

The authors applied the KPR framework to two classic optimization problems, achieving state-of-the-art theoretical guarantees:

Knapsack Median

  • Single-Knapsack: Achieves an approximation factor of approximately $2.733 \times OPT$ with only an $O(1/\gamma)$ additive budget violation.
  • Multi-Knapsack: Achieves a $3.25 \times OPT$ approximation with an $O(\sqrt{m}/\gamma)$ additive violation, where $m$ represents the number of knapsack constraints.

Knapsack Center

For both single and multi-knapsack variants, the algorithm provides a granular "individual fairness" guarantee. Every client is guaranteed a maximum distance of $3 \times OPT$ to a facility, while the expected distance is bounded to approximately $1.74 \times OPT$.

Conclusion and Future Directions

The KPR framework demonstrates that allowing for controlled, additive violations of constraints can lead to significantly better clustering quality and fairness outcomes. Beyond clustering, the authors' new concentration inequality for unbounded random variables represents a significant contribution to probability theory. This tool is potentially applicable to a wide range of problems, including estimating properties in heavy-tailed distributions and analyzing large-scale social networks where variance is difficult to bound. Future work may explore the application of these variance-independent bounds to hypergraph matchings and other complex combinatorial optimization problems.

Summary updated

Abstract

Clustering problems are fundamental to unsupervised learning. There is an increased emphasis on fairness in machine learning and AI; one representative notion of fairness is that no single demographic group should be over-represented among the cluster-centers. This, and much more general clustering problems, can be formulated with "knapsack" and "partition" constraints. We develop new randomized algorithms targeting such problems, and study two in particular: multi-knapsack median and multi-knapsack center. Our rounding algorithms give new approximation and pseudo-approximation algorithms for these problems. One key technical tool, which may be of independent interest, is a new tail bound analogous to Feige (2006) for sums of random variables with unbounded variances. Such bounds can be useful in inferring properties of large networks using few samples.
BibTeX
@misc{harris2017symmetric,
  author = {David G. Harris and Thomas W. Pensyl and Aravind Srinivasan and Khoa Trinh},
  title = {{Symmetric Randomized Dependent Rounding}},
  year = {2017},
  eprint = {1709.06995},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.06995},
}
Figure