Parallel Quasi-concave set optimization: A new frontier that scales without needing submodularity

Praneeth Vepakomma, Yulia Kempner, Ramesh RaskararXiv 2021 · arXiv

Abstract

This paper introduces a parallel algorithm for optimizing induced quasi-concave set functions, offering a robust alternative to submodular optimization. While submodular methods typically provide approximate results, this approach yields globally exact solutions and scales efficiently on parallel hardware, reducing computational complexity from cubic to linear time.

Introduction: Beyond Submodularity

In combinatorial optimization, selecting the optimal subset of items—such as features for a model or sensors for a network—is a recurring challenge. For decades, the framework of submodularity has dominated this field. Submodular functions exhibit a "diminishing returns" property that allows simple greedy algorithms to find solutions within a $1 - 1/e$ (approx. 63%) bound of the optimum. However, for many critical applications, an approximation is insufficient, and finding the exact global optimum for submodular functions is often NP-hard.

This research addresses this gap by focusing on Induced Quasi-concave Set Functions. These functions allow for exact global solutions in subset selection problems, particularly those involving "maxi-min" diversity, without requiring the diminishing returns property.

Theoretical Framework and Duality

The core of this approach lies in the duality between induced quasi-concave functions and monotone linkage functions ($\pi$). A linkage function measures the relationship between an element and a set. It is considered monotone if adding more elements to the set never increases the linkage value for an external element. While optimizing general quasi-concave functions is computationally difficult, the authors demonstrate that functions induced by these monotone linkages are mathematically tractable.

The Parallel Algorithm

The authors propose a parallelized greedy approach to solve the objective: $$\arg \max_{T \subset \mathbf{X}} \min_{X_i \in \mathbf{X} \setminus T} \pi(X_i, T)$$

The algorithm, visualized below, distributes the workload across multiple processors to achieve significant speedups.

The parallel workflow for generating pi-series and identifying the maximal minimal pi-cluster.

The process involves three main stages:

  1. Parallelization: Each element in the ground set is assigned to a processor.
  2. $\pi$-series Generation: Each processor independently builds a sequence of elements (a $\pi$-series) starting from its assigned element.
  3. Global Selection: The algorithm identifies "minimal clusters" from these series and selects the one that maximizes the objective.

Performance and Comparative Analysis

The primary advantage of this method is the combination of global optimality and computational efficiency. By utilizing $n$ processors (where $n$ is the number of elements), the time complexity is reduced from $O(n^3g)$ to $O(n^2g)$. With $n^3$ processors, the complexity can reach $O(gn)$, where $g$ represents the cost of computing the linkage function.

The following table contrasts this method with other common optimization frameworks, highlighting its unique ability to provide globally optimal solutions in polynomial time.

Comparison of optimization types, showing the proposed method's global optimality and complexity.

Practical Application: Distance Covariance

To bridge theory and practice, the authors apply their framework to Distance Covariance, a measure of statistical dependence. They prove that negative squared distance covariance is a monotone linkage function. This allows the algorithm to be used for selecting the most diverse subset of features from tabular datasets, ensuring that even the "weakest link" in the selected subset is as statistically significant as possible.

Conclusion and Future Directions

This work establishes a new frontier in set optimization by providing a scalable, parallelizable path to global optimality. While currently limited to induced quasi-concave functions and requiring significant hardware for maximum speedup, the framework offers a powerful tool for tasks where diversity and robustness are paramount. Future research will explore applications in active learning, private data synthesis, and the summarization of massive datasets.

Summary updated

Abstract

Classes of set functions along with a choice of ground set are a bedrock to determine and develop corresponding variants of greedy algorithms to obtain efficient solutions for combinatorial optimization problems. The class of approximate constrained submodular optimization has seen huge advances at the intersection of good computational efficiency, versatility and approximation guarantees while exact solutions for unconstrained submodular optimization are NP-hard. What is an alternative to situations when submodularity does not hold? Can efficient and globally exact solutions be obtained? We introduce one such new frontier: The class of quasi-concave set functions induced as a dual class to monotone linkage functions. We provide a parallel algorithm with a time complexity over $n$ processors of $\mathcal{O}(n^2g) +\mathcal{O}(\log{\log{n}})$ where $n$ is the cardinality of the ground set and $g$ is the complexity to compute the monotone linkage function that induces a corresponding quasi-concave set function via a duality. The complexity reduces to $\mathcal{O}(gn\log(n))$ on $n^2$ processors and to $\mathcal{O}(gn)$ on $n^3$ processors. Our algorithm provides a globally optimal solution to a maxi-min problem as opposed to submodular optimization which is approximate. We show a potential for widespread applications via an example of diverse feature subset selection with exact global maxi-min guarantees upon showing that a statistical dependency measure called distance correlation can be used to induce a quasi-concave set function.
BibTeX
@misc{vepakomma2021parallel,
  author = {Praneeth Vepakomma and Yulia Kempner and Ramesh Raskar},
  title = {{Parallel Quasi-concave set optimization: A new frontier that scales without needing submodularity}},
  year = {2021},
  eprint = {2108.08758},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2108.08758},
}
Figure