Clustering, dimension reduction, and "data reduction", are all fundamental tools in data analysis and machine learning, each serving as a cornerstone in understanding and organizing complex datasets. Clustering aims to group a collection of points such that points within the same group are "closer" (as measured by some defined metric) compared to points in different groups. This process is critical in various applications, including market segmentation, social network analysis, and image recognition. On the other hand, dimensionality reduction (often achieved via low-rank approximation) seeks to identify the underlying low-dimensional structure in a dataset, assuming such structure exists. This technique is central to applications such as data compression, visualization, and noise reduction. Data reduction, often called "coresets", aims to reduce the size of a dataset, while preserving its essential structure, thereby allowing one to build ML and other models more efficiently.

All three problems have been rigorously explored from the perspective of "approximation algorithms" in several settings. The goal is to design computationally efficient methods that produce solutions whose "cost" —defined based on metrics like within-cluster variance or reconstruction error— is comparable to that of an optimal solution. However, practical constraints often render classical algorithms less suitable for real-world scenarios. This project focused on advancing the state of the art by addressing several practical challenges:

1. Online Arrival Models: In many real-world settings, data points arrive sequentially, necessitating algorithms that make decisions upon the arrival of each point. This contrasts with offline models, where the entire dataset is available upfront. We developed algorithms tailored for this online model, ensuring robust and efficient performance under streaming conditions.

2. Generalized Low-Rank Approximation: Extending beyond classical settings, we addressed significant generalizations, including:
   - Weighted versions: Where points or features carry varying levels of importance.
   - Lp-norm approximations: Providing flexibility by considering alternative norms (e.g., L1 or L-infinity norms) to capture reconstruction error, accommodating a broader range of applications.
   - Matrix completion: Tackling scenarios with missing data, ensuring accurate recovery of the underlying low-rank structure despite incomplete observations.

3. Fairness Constraints: Real-world datasets often contain subpopulations or demographic groups that require equitable treatment. We formulated and solved versions of clustering and low-rank approximation that explicitly incorporate fairness constraints. Here, the aim was to ensure that the "costs" (e.g., clustering or approximation errors) are distributed equitably across groups, mitigating biases inherent in traditional methods.

Beyond these central goals, the project yielded additional notable results:
- We established precise bounds on the size of "spanners"—compact representations of datasets preserving essential geometric properties. Spanners serve as an efficient and interpretable data summary, enabling faster downstream analysis.
- A significant offshoot of this work involved constructing "coresets"—reduced, representative subsets of the data—that satisfy both performance guarantees and fairness constraints. This aspect is particularly valuable for resource-constrained environments where processing the full dataset is infeasible.

The impact of this project is evident through its dissemination in prestigious academic conferences, including NeurIPS, ICML, AISTATS, and FAccT. These venues reflect the relevance of the research, addressing both theoretical foundations and practical implications.

Additionally, the project supported the academic growth of two PhD students, who played pivotal roles in advancing these research directions. They led the development of several publications, gaining expertise and contributing to the broader scientific community. The project also inspired ongoing collaborative efforts, aiming to deepen our understanding of clustering, matrix approximation, and fairness in data analysis. The project also supported curriculum development at the University of Utah, specifically for two courses: Theory of Machine Learning (Spring 2022), and Algorithms, Randomness, and Optimization (Spring 2024). Creating more advanced yet accessible courses has been a priority of the PI (and the Department) to help improve student training, and both of these courses helped achieve this goal.

Last Modified: 01/21/2025
Modified by: Aditya Bhaskara