k-submodular interdiction problems under distributional risk-receptiveness and robustness: application to machine learning

Seonghun Park () and Manish Bansal ()
Additional contact information
Seonghun Park: Virginia Tech
Manish Bansal: Virginia Tech

Computational Management Science, 2025, vol. 22, issue 2, No 8, 37 pages

Abstract: Abstract We study submodular optimization in adversarial context, applicable to machine learning problems such as feature selection using data susceptible to uncertainties and attacks. We focus on Stackelberg zero-sum games (also referred to as interdiction games) between an attacker (or interdictor) and a defender where the attacker aims to minimize the defender’s objective of maximizing a k-submodular function. We allow uncertainties arising from the success of attacks and inherent data noise, and address challenges due to incomplete knowledge of the probability distribution of random parameters. Specifically, we introduce Distributionally Robust k-Submodular Interdiction Problem (DRO k-SIP) and Distributionally Risk-Receptive k-Submodular Interdiction Problem (DRR k-SIP) along with finitely convergent exact algorithms for solving them. When solving the DRO k-SIP, the attacker optimizes their expected payoff with respect to the worst-case probability distribution within the ambiguity set, and thereby have robust attack strategies despite distributional ambiguity. In contrast, the DRR k-SIP identifies attacker strategies with the best-case probability distribution, and identifies critical vulnerabilities for the defender. The optimal values derived from both DRO k-SIP and DRR k-SIP offer a confidence interval-like range for the expected value of the defender’s objective function, capturing distributional ambiguity. We conduct computational experiments on instances of feature selection and sensor placement problems, using Wisconsin breast cancer data and synthetic data, respectively.

Keywords: k-submodular function; Distributionally robust optimization; Distributionally risk-receptive; Feature selection problem; Adversarial machine learning (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10287-025-00541-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:comgts:v:22:y:2025:i:2:d:10.1007_s10287-025-00541-6

Ordering information: This journal article can be ordered from
http://www.springer. ... ch/journal/10287/PS2

DOI: 10.1007/s10287-025-00541-6

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().