Technical Summary: Complement Submodular Information Measures for Balanced and Robust Data Selection

Problem Statement

Submodular optimization has become a standard paradigm for data selection, retrieval, and summarization due to its ability to model coverage, diversity, and representativeness. Classical submodular objectives (e.g., Facility Location, LogDet, Set Cover) optimize the utility of the selected subset in isolation. However, in modern machine learning applications—such as train/validation/test splitting, benchmark construction, and robust subset selection—the quality of a selection often depends critically on the structural relationship between the selected subset and the remaining data (the complement).

Standard objectives suffer from two primary limitations:

1. Representative Bias: Objectives like Facility Location may over-focus on dominant regions or central background structures, neglecting rare or "tail" semantic slices.
2. Diversity Bias: Objectives like LogDet may aggressively select isolated outliers that appear highly dissimilar from the rest of the dataset, failing to preserve coherent rare semantic clusters.

The core problem addressed is the lack of explicit preservation of structural information between a selected subset and its complement, leading to unbalanced selections that either ignore tail distributions or include noisy outliers.

Methodology

Complement Submodular Information (CSI)

The authors introduce Complement Submodular Information (CSI), a unified framework for complement-aware submodular objectives. Given a normalized monotone submodular function $f: 2^V \to \mathbb{R}$ and a subset $A \subseteq V$, the CSI objective is defined as:
$$I_f(A; V \setminus A) = f(A) + f(V \setminus A) - f(V)$$
This formulation acts as a complement-aware analogue to submodular mutual information. It quantifies shared structural information by encouraging the preservation of structure jointly across both the selected subset ($A$) and the remaining data ($V \setminus A$).

Instantiations

The framework induces complement-aware variants of several classical submodular functions:

• Facility Location Complement Information (FLCI): Encourages balanced representative partitioning. A point contributes only if it is well-represented by both the selected subset and its complement.
• Graph Cut Complement Information (GCCI): Measures connectivity across the partition boundary, favoring subsets with strong cross-partition interactions.
• LogDet Complement Information (LogDetCI): Preserves diversity jointly across partitions. It maintains determinant volume on both sides, preserving coherent rare clusters while suppressing isolated outliers that lack support in the complement.
• Probabilistic Set Cover (PSCCI), Saturated Coverage (SCCI), and Feature-Based (FBCI): These variants similarly enforce balanced probabilistic coverage, local neighborhood preservation, and semantic feature activation across both partitions.

Optimization and Theoretical Guarantees

CSI objectives are symmetric and generally non-monotone. However, the authors establish that they exhibit approximate monotonicity under bounded curvature conditions.

• Approximate Monotonicity: The degree of non-monotonicity is controlled by the restricted curvature $\kappa_k(f)$ of the underlying function.
• Greedy Approximation: Under these conditions, the standard greedy algorithm achieves a near-$(1 - 1/e)$ approximation guarantee. Specifically, if $A_g$ is the greedy solution and $A^*$ is the optimal solution:
  $$I_f(A_g; V \setminus A_g) \geq \left(1 - \frac{1}{e}\right) I_f(A^*; V \setminus A^*) - \frac{k\epsilon}{e}$$
  where $\epsilon$ is bounded by the curvature and the maximum marginal gain of the underlying function.
• Efficiency: The paper notes that efficient implementations (e.g., memoization, lazy greedy, rank-one determinant updates) make CSI optimization computationally comparable to standard submodular optimization.

Key Contributions

1. Unified Framework: Introduction of CSI as a systematic framework for complement-aware submodular objectives.
2. Theoretical Analysis: Derivation of complement-aware variants for major submodular functions and proof of near-$(1 - 1/e)$ approximation guarantees for greedy optimization under bounded curvature.
3. Empirical Validation: Demonstration that CSI objectives significantly outperform classical submodular objectives and random baselines in robust hidden-slice-aware subset selection.

Experimental Results

Synthetic Experiments

The authors evaluated CSI objectives on synthetic datasets containing Gaussian clusters of varying sizes (simulating head, medium, and tail semantic regions) and isolated outliers.

• Metrics: Minority Coverage Ratio, Outlier Selection Rate, and KL divergence between selected/complement/full distributions.
• Findings:
  • Balanced Preservation: CSI variants (FLCI, LogDetCI, SCCI, FBCI) consistently improved the coverage of rare/tail semantic slices compared to their standard counterparts.
  • Outlier Suppression: While standard LogDet aggressively selected outliers, LogDetCI reduced outlier selection rates by nearly a factor of three while preserving rare modes.
  • Representative Balance: FLCI and SCCI achieved superior balance between representative coverage and robustness, minimizing the KL divergence between the selected subset and the full dataset.
  • Graph Cut Limitation: GCCI was found to favor dense, highly connected head regions rather than balanced semantic coverage, making it less suitable for representative preservation in this context.

Robust Hidden-Slice-Aware Subset Selection

The framework was tested on six real-world datasets (MNIST, FashionMNIST, CIFAR10, Digits, HAR, 20Newsgroups) with latent semantic slices and injected noise.

• Setup: Subsets were selected without access to slice labels (unsupervised clustering used only for evaluation). Downstream models were trained on these subsets.
• Results: CSI objectives (specifically FLCI, LogDetCI, and SCCI) consistently achieved higher downstream classification accuracy than random selection, stratified selection, and the underlying standard submodular objectives.
• Insight: The performance gains were attributed to the ability of CSI to preserve coherent rare semantic structures while simultaneously suppressing noisy and isolated outliers, a balance that standard objectives failed to achieve.

Significance and Claims

The paper claims that preserving structural information jointly across a selected subset and its complement leads to substantially more balanced and robust data selections than optimizing the subset alone. The significance of this work lies in:

1. Addressing a Structural Gap: Moving beyond the optimization of the selected subset in isolation to explicitly model the relationship with the complement.
2. Practical Robustness: Providing a method that naturally regularizes the tendency of classical objectives to either over-focus on dominant regions or select outliers, thereby improving downstream predictive performance in the presence of hidden semantic imbalances and noise.
3. Theoretical Soundness: Establishing that despite being non-monotone, these objectives remain tractable with strong theoretical approximation guarantees.

The authors conclude that CSI offers a unified approach to achieving balanced preservation of head and tail semantic structures, making it particularly effective for applications requiring robust subset selection and fair data splitting.