Complement Submodular Information Measures for Balanced and Robust Data Selection

• URL: http://arxiv.org/abs/2605.24779v1
• Date: Sat, 23 May 2026 23:43:24 GMT
• Title: Complement Submodular Information Measures for Balanced and Robust Data Selection
• Abstract summary: Complement Submodular Information (CSI) is a new class of complement-aware submodular objectives.<n>We show that CSI objectives consistently outperform standard submodular objectives on robust subset selection.<n>In particular, CSI objectives significantly improve preservation of coherent rare/tail semantic structure.
• Score: 0.20305676256390934
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Submodular optimization has become a fundamental paradigm for data selection, retrieval, summarization, and representation learning due to its ability to model coverage, diversity, and representativeness. However, classical submodular objectives optimize only the selected subset and do not explicitly preserve structural information between the selected subset and the remaining data. In many modern machine learning applications, including train/validation/test splitting, benchmark construction, and robust subset selection, the quality of a selection depends critically on preserving balanced structure across both the selected subset and its complement. In this work, we introduce Complement Submodular Information (CSI), a new class of complement-aware submodular objectives that quantify shared structural information between a subset and its complement. Our framework induces complement-aware variants of several classical submodular functions including Facility Location, Graph Cut, LogDet, Saturated Coverage, Set Cover, Probabilistic Set Cover, and Feature Based Functions. We analyze the theoretical properties of CSI objectives and show that they exhibit approximate monotonicity under bounded curvature conditions, leading to near-$(1-1/e)$ greedy approximation guarantees. Empirically, CSI objectives consistently outperform standard submodular objectives on robust hidden-slice-aware subset selection. In particular, CSI objectives significantly improve preservation of coherent rare/tail semantic structure while simultaneously suppressing noisy and isolated outliers, leading to substantially improved downstream predictive performance. Synthetic experiments further illustrate how different CSI instantiations capture complementary notions of representativeness, diversity, connectivity, and balanced neighborhood preservation.

Related papers

• Objective-Induced Bias and Search Dynamics in Multiobjective Unsupervised Feature Selection [2.2282508171588806]
  We study the choice of evaluation objective, the direction of subset-size regularisation, and the initialisation strategy.<n>We show that objective design is central to effective multiobjective unsupervised feature selection.
  arXiv  Detail & Related papers  (2026-05-20T15:14:00Z)
• Quantum Feature Selection with Higher-Order Binary Optimization on Trapped-Ion Hardware [4.622928173506349]
  We present a quantum feature-selection framework based on a higher-order unconstrained binary optimization (HUBO) formulation.<n>The proposed model includes one-, two-, and three-body interaction terms derived from mutual-information measures.<n>We evaluate the proposed workflow on two benchmark classification datasets, namely the Gallstone dataset and the Spambase dataset.
  arXiv  Detail & Related papers  (2026-04-29T16:01:39Z)
• USBD: Universal Structural Basis Distillation for Source-Free Graph Domain Adaptation [28.47018372381707]
  SF-GDA is pivotal for privacy-preserving knowledge transfer across graph datasets.<n>We propose the Universal Structural Basis Distillation, a framework that shifts the paradigm from adapting a biased model to learning a universal structural basis for SF-GDA.
  arXiv  Detail & Related papers  (2026-02-09T09:39:07Z)
• Improving Set Function Approximation with Quasi-Arithmetic Neural Networks [23.73257235603082]
  We propose quasi-arithmetic neural networks (QUANNs)<n>QUANNs are universal approximators for a broad class of common set-function decompositions.<n>We provide a theoretical analysis showing that, QUANNs are universal approximators for a broad class of common set-function decompositions.
  arXiv  Detail & Related papers  (2026-02-04T18:36:31Z)
• Spatial-Temporal-Spectral Unified Modeling for Remote Sensing Dense Prediction [20.1863553357121]
  Current deep learning architectures for remote sensing are fundamentally rigid.<n>We introduce the Spatial-Temporal-Spectral Unified Network (STSUN) for unified modeling.<n> STSUN can adapt to input and output data with arbitrary spatial sizes, temporal lengths, and spectral bands.<n>It unifies various dense prediction tasks and diverse semantic class predictions.
  arXiv  Detail & Related papers  (2025-05-18T07:39:17Z)
• Structural Entropy Guided Probabilistic Coding [52.01765333755793]
  We propose a novel structural entropy-guided probabilistic coding model, named SEPC.<n>We incorporate the relationship between latent variables into the optimization by proposing a structural entropy regularization loss.<n> Experimental results across 12 natural language understanding tasks, including both classification and regression tasks, demonstrate the superior performance of SEPC.
  arXiv  Detail & Related papers  (2024-12-12T00:37:53Z)
• Enhancing Neural Subset Selection: Integrating Background Information into Set Representations [53.15923939406772]
  We show that when the target value is conditioned on both the input set and subset, it is essential to incorporate an textitinvariant sufficient statistic of the superset into the subset of interest. This ensures that the output value remains invariant to permutations of the subset and its corresponding superset, enabling identification of the specific superset from which the subset originated.
  arXiv  Detail & Related papers  (2024-02-05T16:09:35Z)
• BOtied: Multi-objective Bayesian optimization with tied multivariate ranks [33.414682601242006]
  In this paper, we show a natural connection between non-dominated solutions and the extreme quantile of the joint cumulative distribution function. Motivated by this link, we propose the Pareto-compliant CDF indicator and the associated acquisition function, BOtied. Our experiments on a variety of synthetic and real-world problems demonstrate that BOtied outperforms state-of-the-art MOBO acquisition functions.
  arXiv  Detail & Related papers  (2023-06-01T04:50:06Z)
• Disentanglement via Latent Quantization [60.37109712033694]
  In this work, we construct an inductive bias towards encoding to and decoding from an organized latent space. We demonstrate the broad applicability of this approach by adding it to both basic data-re (vanilla autoencoder) and latent-reconstructing (InfoGAN) generative models.
  arXiv  Detail & Related papers  (2023-05-28T06:30:29Z)
• CoADNet: Collaborative Aggregation-and-Distribution Networks for Co-Salient Object Detection [91.91911418421086]
  Co-Salient Object Detection (CoSOD) aims at discovering salient objects that repeatedly appear in a given query group containing two or more relevant images. One challenging issue is how to effectively capture co-saliency cues by modeling and exploiting inter-image relationships. We present an end-to-end collaborative aggregation-and-distribution network (CoADNet) to capture both salient and repetitive visual patterns from multiple images.
  arXiv  Detail & Related papers  (2020-11-10T04:28:11Z)
• Out-of-distribution Generalization via Partial Feature Decorrelation [72.96261704851683]
  We present a novel Partial Feature Decorrelation Learning (PFDL) algorithm, which jointly optimize a feature decomposition network and the target image classification model. The experiments on real-world datasets demonstrate that our method can improve the backbone model's accuracy on OOD image classification datasets.
  arXiv  Detail & Related papers  (2020-07-30T05:48:48Z)
• Target-Embedding Autoencoders for Supervised Representation Learning [111.07204912245841]
  This paper analyzes a framework for improving generalization in a purely supervised setting, where the target space is high-dimensional. We motivate and formalize the general framework of target-embedding autoencoders (TEA) for supervised prediction, learning intermediate latent representations jointly optimized to be both predictable from features as well as predictive of targets.
  arXiv  Detail & Related papers  (2020-01-23T02:37:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.