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 process involves three main stages:
- Parallelization: Each element in the ground set is assigned to a processor.
- $\pi$-series Generation: Each processor independently builds a sequence of elements (a $\pi$-series) starting from its assigned element.
- 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.
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