Toward Trustworthy AI: Multi-Target Adversarial Attacks and Robust Defenses for Continuous Data Summarization

# Toward Trustworthy AI: Multi-Target Adversarial Attacks and Robust Defenses for Continuous Data Summarization
Source: [https://arxiv.org/html/2606.11804](https://arxiv.org/html/2606.11804)
Yuefang Lian, Longkun Guo†,‡, , Zhongrui Zhao†, Zhigang Lu, , Yanan Cai, Shuchao Pang, , Dachuan Xu, Jason XueManuscript received April 19, 2021; revised August 16, 2021\.†\\dagger: equal contribution,‡\\ddagger: corresponding authorYuefang Lian is with Nankai University, Tianjin, China\. This work was done when Yuefang was a visiting PhD student with James Cook University and Western Sydney University during PhD candidature at Beijing University of Technology\.Longkun Guo is with Fuzhou University, Fuzhou, China\.Zhongrui Zhao and Yanan Cai are with James Cook University, Townsville, Australia and Western Sydney University, Sydney, Australia\.Zhigang Lu is with Western Sydney University, Sydney, Australia\. This work was partially done when Zhigang was a Lecturer with James Cook University\.Shuchao Pang is with Nanjing University of Science and Technology, Nanjing, China\.Dachuan Xu is with Beijing University of Technology, Beijing, China\.Jason Xue is with CSIRO’s Data 61, Sydney, Australia and Responsible AI Research \(RAIR\) Centre, The University of Adelaide, Australia\.

###### Abstract

Trustworthy AI requires reliable data\-processing pipelines, not only robust downstream predictive models\. As an upstream component, data summarization determines which information is retained and passed to subsequent learning or decision modules\. Therefore, adversarial perturbations to the summarization process can compromise trustworthy AI in an upstream manner: they may alter the selected summary, reduce its representativeness, and further degrade the utility of subsequent learning tasks\. In this paper, we study adversarial attacks on continuous data summarization under similarity\-level perturbations through DR\-submodular optimization\. We show that a class of multi\-resolution image summarization objectives can be formulated as multilinear extensions of non\-negative submodular set functions and satisfy DR\-submodularity withmm\-weak monotonicity\. We then formulate multi\-target attack generation as a min\-max problem, where one admissible perturbation of the similarity structure is optimized to degrade multiple target summarization models\. To mitigate such perturbations, we formulate robust defense against mixed attack types as a regularized max\-min problem\. For both problems, we develop approximation algorithms with theoretical guarantees\. Experiments on real\-data and controlled clustered benchmarks show that the proposed attack is effective in representative low\-to\-moderate budget regimes and can induce downstream task\-performance loss\. The proposed defense improves the robustness–mitigation trade\-off in structured settings, while also revealing the parameter sensitivity of robust protection on real data\.

## IIntroduction

Trustworthy AI requires the reliability of the entire data\-processing pipeline, not only the robustness of downstream predictive models\. In many AI systems, data summarization and sample selection are used as upstream components to extract representative information before training, retrieval, storage, or decision making\. Although these procedures are often treated as benign preprocessing steps, they determine which data are retained and passed to subsequent modules\. Therefore, adversarial perturbations to the summarization process may compromise trustworthy AI in an upstream manner: they can remove representative information, increase redundancy, distort the selected training or retrieval set, and eventually reduce downstream task reliability\. This makes adversarial robustness of data summarization a security\-relevant problem for trustworthy AI pipelines\.

Continuous submodular maximization provides a natural mathematical framework for modeling summarization and selection tasks\. Classical results on submodular functions and multilinear relaxations\[[16](https://arxiv.org/html/2606.11804#bib.bib85),[4](https://arxiv.org/html/2606.11804#bib.bib86)\]established the importance of diminishing\-returns structure in discrete and continuous optimization, and subsequent studies have used this structure for budget allocation, data summarization, and representative selection\[[19](https://arxiv.org/html/2606.11804#bib.bib48),[18](https://arxiv.org/html/2606.11804#bib.bib13),[8](https://arxiv.org/html/2606.11804#bib.bib14)\]\. Submodular optimization has also appeared in security\-related data\-processing problems, such as attack detection scheduling in large\-scale networks under false data injection attacks\[[22](https://arxiv.org/html/2606.11804#bib.bib4)\]\. However, these works do not study adversarial vulnerability of the summarization process itself as an upstream component in trustworthy AI pipelines\.

This upstream vulnerability becomes particularly relevant in similarity\-based continuous summarization\. Many summarization objectives are constructed from pairwise similarities or feature\-induced similarity scores, and the summarizer optimizes a soft selection vector based on this similarity structure\. Thus, the similarity\-construction stage naturally becomes an attack surface: an adversary may perturb the similarity matrix without directly modifying the final summary decision variable\. Such perturbations may arise from manipulated feature representations in retrieval\-style systems or poisoned samples that alter neighborhood\- or similarity\-based structures\[[24](https://arxiv.org/html/2606.11804#bib.bib2),[5](https://arxiv.org/html/2606.11804#bib.bib1)\]\. After the summarization module is executed on the perturbed objective, the selected summary may become less representative when evaluated under the original clean objective\. The risk is further amplified in multi\-target settings, where several summarization models may be built from related data sources or similar feature representations\. In such cases, a single perturbation to the upstream similarity structure may simultaneously degrade multiple target summarization models, motivating a multi\-target attack formulation for similarity\-based continuous summarization\.

Existing studies on adversarial attacks and robust optimization provide important foundations, but they do not directly address the setting considered in this paper\. On the attack side, prior work has studied adversarial sample generation for discrete submodular optimization\[[1](https://arxiv.org/html/2606.11804#bib.bib45),[12](https://arxiv.org/html/2606.11804#bib.bib78)\]and general non\-convex min\-max formulations\[[25](https://arxiv.org/html/2606.11804#bib.bib44)\]\. However, these methods do not explicitly model the combination of continuity, DR\-submodularity, andmm\-weak monotonicity that arises in the continuous summarization problem considered here, nor do they focus on generating one shared perturbation that attacks multiple summarization models simultaneously\. On the defense side, robust submodular optimization has been studied for set functions, monotone continuous models, and general non\-convex robust formulations\[[20](https://arxiv.org/html/2606.11804#bib.bib47),[11](https://arxiv.org/html/2606.11804#bib.bib8),[13](https://arxiv.org/html/2606.11804#bib.bib7),[25](https://arxiv.org/html/2606.11804#bib.bib44)\]\. Yet these methods do not explicitly address robust protection for weakly monotone DR\-submodular summarization models under mixed similarity\-level attack types\. As a result, the attack and defense mechanisms of continuous summarization remain insufficiently understood, especially from the perspective of downstream reliability in trustworthy AI pipelines\.

In this paper, we study the adversarial vulnerability and robust protection of continuous data summarization under perturbations of the upstream similarity structure\. Instead of directly modifying the final summary decision, the adversary perturbs the similarity matrix that defines the summarization objective\. This similarity\-level threat model captures an upstream attack surface in trustworthy AI pipelines, where degraded summaries may affect the representative information passed to downstream modules\. To address this issue, we develop a DR\-submodular optimization framework for multi\-target attack generation and robust defense, and evaluate it on real\-data multilinear\-extension summarization and a controlled clustered multi\-target benchmark\. The former tests the theory\-aligned objective on real data, while the latter provides an interpretable setting for analyzing the attack mechanism and downstream consequences through known cluster and representative structure\.

Contributions\.The main contributions of this paper are summarized as follows\.

- •We provide a DR\-submodular formulation for a class of multi\-resolution image summarization objectives\. Specifically, we show that the corresponding discrete utility is non\-negative, submodular, andmm\-weakly monotone under a controlled redundancy condition, and that its multilinear extension preserves non\-negativity, DR\-submodularity, and weak monotonicity\.
- •We introduce a similarity\-level threat model for continuous data summarization, where the adversary perturbs the upstream similarity structure rather than directly modifying the final summary decision\. Under this model, we formulate multi\-target attack generation for data summarization as a structured min\-max optimization problem and develop a structure\-aware approximation algorithm for constructing one shared perturbation across multiple target summarization models\.
- •We formulate robust defense against admissible similarity\-level perturbations as a regularized max\-min optimization problem\. We develop a robust continuous grtype algorithm formm\-weakly monotone DR\-submodular objectives and establish an approximation guarantee under standard smoothness\.
- •We conduct empirical evaluations on real\-data multilinear\-extension summarization and a controlled clustered multi\-target benchmark\. The results show that optimized similarity perturbations can induce measurable summarization degradation in representative budget regimes\. Downstream evaluations further demonstrate that such degradation can translate into task\-level performance loss, and that robust summaries can recover downstream reliability by restoring class/cluster coverage\. These findings connect adversarial summarization to the reliability of trustworthy AI pipelines\.

## IIRelated Work

This section reviews prior work related to adversarial attack generation and robust optimization in submodular settings, with an emphasis on their relevance to secure data processing and trustworthy AI\.

### II\-AAttack Generation with Submodular Structure

Attack generation has been studied in several optimization and security\-related settings where submodular structure is used to model diminishing returns in perturbation, selection, or degradation effects\. In DC microgrids, Liu et al\.\[[15](https://arxiv.org/html/2606.11804#bib.bib5)\]leveraged submodular structure to construct false data injection attacks by exploiting the submodularity of system state error\. Zhu et al\.\[[29](https://arxiv.org/html/2606.11804#bib.bib3)\]studied attacks that degrade network robustness through edge perturbations, using greedy optimization for robustness\-related objectives\. In text classification, Lei et al\.\[[12](https://arxiv.org/html/2606.11804#bib.bib78)\]showed that the perturbation search space for attacking certain neural models exhibits submodularity, allowing attack generation to be formulated as a submodular optimization problem\. More closely related to our setting, Adibi et al\.\[[1](https://arxiv.org/html/2606.11804#bib.bib45)\]studied convex\-submodular min\-max optimization and obtained theoretical guarantees for discrete submodular attack generation and the multilinear extension of monotone set\-submodular functions\. In a different direction, Wang et al\.\[[25](https://arxiv.org/html/2606.11804#bib.bib44)\]considered adversarial attack generation from a general non\-convex min\-max optimizaton perspective and analyzed convergence toward stationary solutions\.

These works provide important foundations for studying adversarial vulnerability in structured optimization problems\. However, they do not explicitly address the setting considered here, where the attack target consists of multiple continuous summarization models with DR\-submodularity andmm\-weak monotonicity, and where the goal is to construct a single perturbation that simultaneously degrades several target summarization models\. Our work complements these lines of research by focusing on adversarial robustness evaluation for continuous data summarization, a security\-relevant component of trustworthy AI pipelines\.

### II\-BRobust Submodular Optimization

Robust submodular optimization has been studied in several important application domains, including observation selection\[[9](https://arxiv.org/html/2606.11804#bib.bib63)\]and influence maximization\[[6](https://arxiv.org/html/2606.11804#bib.bib60),[7](https://arxiv.org/html/2606.11804#bib.bib61)\]\. These works typically consider maximizing the worst\-case value over a family of submodular set functions\. Another relevant line studies robust optimization in adversarial non\-convex settings, where problems are formulated as nonconvex\-concave saddle\-point problems and solved by exploiting connections to continuous submodularity\[[20](https://arxiv.org/html/2606.11804#bib.bib47)\], with extensions to security games\[[26](https://arxiv.org/html/2606.11804#bib.bib64)\]and distributionally robust settings\[[21](https://arxiv.org/html/2606.11804#bib.bib62)\]\.

For continuous submodular optimization, Lee et al\.\[[11](https://arxiv.org/html/2606.11804#bib.bib8)\]studied non\-smooth and Hölder\-smooth submodular maximization and derived approximation guarantees that can be used in robust formulations\. Lian et al\.\[[13](https://arxiv.org/html/2606.11804#bib.bib7)\]proposed a zeroth\-order approximation algorithm for robust DR\-submodular maximization by solving a non\-smooth up\-concave optimization problem\. Wang et al\.\[[25](https://arxiv.org/html/2606.11804#bib.bib44)\]also considered robust optimization against mixed adversarial attacks in a general non\-convex setting, but the resulting guarantees are given in terms of stationary solutions\. These works are closely related to the defense side of our problem, but they do not explicitly address robust protection for continuous DR\-submodular summarization models withmm\-weak monotonicity under mixed attack types\. Our work extends this literature by studying robust protection for an upstream data summarization component in trustworthy AI pipelines, where adversarial perturbations may affect multiple target summarization models simultaneously\.

Table[I](https://arxiv.org/html/2606.11804#S2.T1)summarizes representative theoretical frameworks related to our attack and defense formulations\. This table is intended to clarify differences in modeling assumptions and guarantee types; it is not an empirical baseline list, since several methods rely on monotonicity or single\-target formulations and are therefore not directly applicable to our weakly monotone multi\-target summarization setting\.

TABLE I:Positioning of representative optimization frameworks related to attack generation and robust defense\.Ref\.RoleModel settingCont\.Multi\-target / mixedGuaranteeRelation to this work\[[1](https://arxiv.org/html/2606.11804#bib.bib45)\]AttackSet submodular, monotoneNoNo\(1−1/e\)\(1\-1/e\)\-approx\.Discrete, single\-target\[[1](https://arxiv.org/html/2606.11804#bib.bib45)\]AttackMultilinear extension, monotoneYesNo\(1/2\)\(1/2\)\-approx\.Continuous but monotone and single\-target\[[25](https://arxiv.org/html/2606.11804#bib.bib44)\]AttackGeneral non\-convex min\-maxYesYesStationary pointBaseline, no DR\-submodular ratio\[[11](https://arxiv.org/html/2606.11804#bib.bib8)\]DefenseDR\-submodular, monotoneYesNo\(1/2\)\(1/2\)\-approx\.Monotone model, no mixed attack defense\[[13](https://arxiv.org/html/2606.11804#bib.bib7)\]DefenseDR\-submodular, monotoneYesNo\(1−1/e\)\(1\-1/e\)\-approx\.Monotone robust DR\-submodular setting\[[25](https://arxiv.org/html/2606.11804#bib.bib44)\]DefenseGeneral non\-convex robustYesYesStationary pointHandles mixed attacks, stationary guaranteesThis workAttack / defenseDR\-submodular,mm\-weakly monotoneYesYesm​\(1−1/e\)m\(1\-1/e\)\-approx\.Continuous weakly monotone summarization with multi\-target attack and mixed defense

## IIIPreliminaries

### III\-ABasic Notation and Structural Properties

For𝐱,𝐲∈ℝn\\mathbf\{x\},\\mathbf\{y\}\\in\\mathbb\{R\}^\{n\}, we denote\(𝐱∨𝐲\)i=max⁡\{𝐱i,𝐲i\}\(\\mathbf\{x\}\\vee\\mathbf\{y\}\)\_\{i\}=\\max\\\{\\mathbf\{x\}\_\{i\},\\mathbf\{y\}\_\{i\}\\\}and\(𝐱∧𝐲\)i=min⁡\{𝐱i,𝐲i\}\(\\mathbf\{x\}\\wedge\\mathbf\{y\}\)\_\{i\}=\\min\\\{\\mathbf\{x\}\_\{i\},\\mathbf\{y\}\_\{i\}\\\}\. Moreover,𝐱≤𝐲\\mathbf\{x\}\\leq\\mathbf\{y\}means that𝐱i≤𝐲i\\mathbf\{x\}\_\{i\}\\leq\\mathbf\{y\}\_\{i\}for alli∈\[n\]i\\in\[n\]\. We first recall the definition of continuous DR\-submodularity\.

###### Definition 1\(DR\-submodularity\[[3](https://arxiv.org/html/2606.11804#bib.bib49)\]\)\.

Given a convex set𝒟⊆ℝn\\mathcal\{D\}\\subseteq\\mathbb\{R\}^\{n\}, a continuous functionf:𝒟→ℝf:\\mathcal\{D\}\\rightarrow\\mathbb\{R\}is said to be DR\-submodular over𝒟\\mathcal\{D\}if, for any𝐱≤𝐲∈𝒟\\mathbf\{x\}\\leq\\mathbf\{y\}\\in\\mathcal\{D\}and anya∈ℝ\+a\\in\\mathbb\{R\}\_\{\+\}such thata​𝐞i\+𝐱∈𝒟a\\mathbf\{e\}\_\{i\}\+\\mathbf\{x\}\\in\\mathcal\{D\}anda​𝐞i\+𝐲∈𝒟a\\mathbf\{e\}\_\{i\}\+\\mathbf\{y\}\\in\\mathcal\{D\}, the following diminishing\-returns property holds for everyi∈\{1,…,n\}i\\in\\\{1,\\dots,n\\\}:

f​\(a​𝐞i\+𝐱\)−f​\(𝐱\)≥f​\(a​𝐞i\+𝐲\)−f​\(𝐲\)\.f\(a\\mathbf\{e\}\_\{i\}\+\\mathbf\{x\}\)\-f\(\\mathbf\{x\}\)\\geq f\(a\\mathbf\{e\}\_\{i\}\+\\mathbf\{y\}\)\-f\(\\mathbf\{y\}\)\.

Throughout the paper, the feasible set𝒳\\mathcal\{X\}is assumed to be a down\-closed convex set, namely, if𝐱∈𝒳\\mathbf\{x\}\\in\\mathcal\{X\}and𝟎≤𝐲≤𝐱\\mathbf\{0\}\\leq\\mathbf\{y\}\\leq\\mathbf\{x\}, then𝐲∈𝒳\\mathbf\{y\}\\in\\mathcal\{X\}\. We also assume that the objective function is non\-negative\. To characterize DR\-submodular functions that are not fully monotone, we use the notion ofmm\-weak monotonicity over continuous domains, extending the corresponding concept for set functions in\[[17](https://arxiv.org/html/2606.11804#bib.bib82)\]\.

###### Definition 2\(mm\-weakly monotone\)\.

For the maximization of a non\-negative continuous functionffover a feasible set𝒳\\mathcal\{X\}, we say thatffismm\-weakly monotone if

f​\(𝐱∨𝐲\)≥m​f​\(𝐱\),∀𝐱,𝐲∈𝒳\.f\(\\mathbf\{x\}\\vee\\mathbf\{y\}\)\\geq mf\(\\mathbf\{x\}\),\\qquad\\forall\\mathbf\{x\},\\mathbf\{y\}\\in\\mathcal\{X\}\.

Whenm=1m=1, the above definition reduces to standard monotonicity, i\.e\.,f​\(𝐱∨𝐲\)≥f​\(𝐱\)f\(\\mathbf\{x\}\\vee\\mathbf\{y\}\)\\geq f\(\\mathbf\{x\}\)for all𝐱,𝐲∈𝒳\\mathbf\{x\},\\mathbf\{y\}\\in\\mathcal\{X\}\. For additional properties of DR\-submodular functions and examples ofmm\-weak monotonicity, we refer readers to\[[3](https://arxiv.org/html/2606.11804#bib.bib49),[17](https://arxiv.org/html/2606.11804#bib.bib82)\]\. For constrained maximization problems, we use the standard notion of an\(α,ϵ\)\(\\alpha,\\epsilon\)\-approximation, meaning that the returned solution achieves at least anα\\alphafraction of the optimal value up to an additive errorϵ\\epsilon, i\.e\.,f​\(𝐱output\)≥α​f​\(𝐱∗\)−ϵf\(\\mathbf\{x\}\_\{\\rm output\}\)\\geq\\alpha f\(\\mathbf\{x\}^\{\*\}\)\-\\epsilon, where𝐱∗\\mathbf\{x\}^\{\*\}is an optimal solution,α∈\(0,1\]\\alpha\\in\(0,1\]is the approximation ratio, andϵ≥0\\epsilon\\geq 0is the optimization accuracy\.

### III\-BMulti\-Resolution Image Summarization Model

We instantiate our study through multi\-resolution image summarization, which serves as a representative upstream data summarization model in trustworthy AI pipelines\. Given a datasetΩ\\Omegawith\|Ω\|=n\|\\Omega\|=n, the goal is to select a subset of representative images that provides good coverage of the dataset while avoiding excessive redundancy\. Instead of optimizing directly over discrete subsets, we adopt a continuous relaxation in which each coordinatexν∈\[0,1\]x\_\{\\nu\}\\in\[0,1\]represents the probability or soft weight of selecting imageν\\nu\. After optimization, a deterministic summary can be obtained either by thresholding, e\.g\.,

Sτ=\{ν∈Ω:xν≥τ\},S\_\{\\tau\}=\\\{\\nu\\in\\Omega:x\_\{\\nu\}\\geq\\tau\\\},or by selecting the top\-ranked images according to\{xν\}ν∈Ω\\\{x\_\{\\nu\}\\\}\_\{\\nu\\in\\Omega\}\.

We first define the corresponding discrete summarization utility\. For a subsetS⊆ΩS\\subseteq\\Omega, let

f​\(S,Ω\)=r​\(S,Ω\)−λn​q​\(S,Ω\),f\(S,\\Omega\)=r\(S,\\Omega\)\-\\frac\{\\lambda\}\{n\}q\(S,\\Omega\),\(1\)where

r​\(S,Ω\)=∑μ∈Ωmaxν∈S⁡sμ,νr\(S,\\Omega\)=\\sum\_\{\\mu\\in\\Omega\}\\max\_\{\\nu\\in S\}s\_\{\\mu,\\nu\}is the facility\-location representativeness term, and

q​\(S,Ω\)=∑μ∈S∑ν∈S,ν≠μsμ,νq\(S,\\Omega\)=\\sum\_\{\\mu\\in S\}\\sum\_\{\\nu\\in S,\\,\\nu\\neq\\mu\}s\_\{\\mu,\\nu\}is the redundancy penalty\. Heresμ,ν≥0s\_\{\\mu,\\nu\}\\geq 0denotes the similarity between imagesμ\\muandν\\nu, andλ≥0\\lambda\\geq 0controls the strength of the redundancy penalty\. For the empty set, we adopt the conventionmaxν∈∅⁡sμ,ν=0\\max\_\{\\nu\\in\\emptyset\}s\_\{\\mu,\\nu\}=0, and hencef​\(∅,Ω\)=0f\(\\emptyset,\\Omega\)=0\.

The first term rewards selected images that well represent the remaining data points, while the second term discourages the simultaneous selection of highly similar images\. To ensure that the redundancy penalty does not dominate the representativeness term, we define the redundancy\-to\-representativeness ratio

ρΩ=sup∅≠S⊆Ωλn​q​\(S,Ω\)r​\(S,Ω\)\.\\rho\_\{\\Omega\}=\\sup\_\{\\emptyset\\neq S\\subseteq\\Omega\}\\frac\{\\frac\{\\lambda\}\{n\}q\(S,\\Omega\)\}\{r\(S,\\Omega\)\}\.Throughout this paper, we assume thatr​\(S,Ω\)\>0r\(S,\\Omega\)\>0for every nonempty feasible setSSand that0≤ρΩ<10\\leq\\rho\_\{\\Omega\}<1\. This condition means that the redundancy penalty is controlled relative to the coverage utility\. Under this assumption, we have thatf​\(S,Ω\)≥0f\(S,\\Omega\)\\geq 0for allS⊆ΩS\\subseteq\\Omega\.

The continuous objective studied in this paper is defined as the multilinear extension of the discrete utility in \([1](https://arxiv.org/html/2606.11804#S3.E1)\)\. Specifically, for𝐱∈\[0,1\]n\\mathbf\{x\}\\in\[0,1\]^\{n\}, letS∼𝐱S\\sim\\mathbf\{x\}denote a random subset ofΩ\\Omegain which each imageν\\nuis independently selected with probabilityxνx\_\{\\nu\}\. We define

F​\(𝐱,Ω\)=𝔼S∼𝐱​\[f​\(S,Ω\)\]\.F\(\\mathbf\{x\},\\Omega\)=\\mathbb\{E\}\_\{S\\sim\\mathbf\{x\}\}\\left\[f\(S,\\Omega\)\\right\]\.\(2\)Equivalently,F​\(𝐱,Ω\)=Rmulti​\(𝐱,Ω\)−Qmulti​\(𝐱,Ω\),F\(\\mathbf\{x\},\\Omega\)=R\_\{\\mathrm\{multi\}\}\(\\mathbf\{x\},\\Omega\)\-Q\_\{\\mathrm\{multi\}\}\(\\mathbf\{x\},\\Omega\),where

Rmulti​\(𝐱,Ω\)=∑μ∈Ω𝔼S∼𝐱​\[maxν∈S⁡sμ,ν\],R\_\{\\mathrm\{multi\}\}\(\\mathbf\{x\},\\Omega\)=\\sum\_\{\\mu\\in\\Omega\}\\mathbb\{E\}\_\{S\\sim\\mathbf\{x\}\}\\left\[\\max\_\{\\nu\\in S\}s\_\{\\mu,\\nu\}\\right\],and

Qmulti​\(𝐱,Ω\)=λn​∑μ∈Ω∑ν∈Ω,ν≠μxμ​xν​sμ,ν\.Q\_\{\\mathrm\{multi\}\}\(\\mathbf\{x\},\\Omega\)=\\frac\{\\lambda\}\{n\}\\sum\_\{\\mu\\in\\Omega\}\\sum\_\{\\nu\\in\\Omega,\\,\\nu\\neq\\mu\}x\_\{\\mu\}x\_\{\\nu\}s\_\{\\mu,\\nu\}\.The expression forQmultiQ\_\{\\mathrm\{multi\}\}follows from the independence of the random selections, since𝔼​\[𝟏μ∈S​𝟏ν∈S\]=xμ​xν\\mathbb\{E\}\[\\mathbf\{1\}\_\{\\mu\\in S\}\\mathbf\{1\}\_\{\\nu\\in S\}\]=x\_\{\\mu\}x\_\{\\nu\}, whereμ≠ν\\mu\\neq\\nu\.

The following lemma shows that the continuous objective belongs to the structural class studied in this paper\.

###### Lemma 1\(Proof in Sec\.[\-A2](https://arxiv.org/html/2606.11804#A0.SS1.SSS2)\)\.

Suppose thatsμ,ν≥0s\_\{\\mu,\\nu\}\\geq 0for allμ,ν∈Ω\\mu,\\nu\\in\\Omega, and define

ρΩ=sup∅≠S⊆Ωλn​q​\(S,Ω\)r​\(S,Ω\)\.\\rho\_\{\\Omega\}=\\sup\_\{\\emptyset\\neq S\\subseteq\\Omega\}\\frac\{\\frac\{\\lambda\}\{n\}q\(S,\\Omega\)\}\{r\(S,\\Omega\)\}\.Assume thatr​\(S,Ω\)\>0r\(S,\\Omega\)\>0for every nonempty feasible setSSand that0≤ρΩ<10\\leq\\rho\_\{\\Omega\}<1\. Then the discrete utilityf​\(S,Ω\)f\(S,\\Omega\)defined in \([1](https://arxiv.org/html/2606.11804#S3.E1)\) is non\-negative, submodular, andmΩm\_\{\\Omega\}\-weakly monotone withmΩ=1−ρΩm\_\{\\Omega\}=1\-\\rho\_\{\\Omega\}\. Consequently, its multilinear extensionF​\(𝐱,Ω\)F\(\\mathbf\{x\},\\Omega\)defined in \([2](https://arxiv.org/html/2606.11804#S3.E2)\) is non\-negative, DR\-submodular over\[0,1\]n\[0,1\]^\{n\}, andmΩm\_\{\\Omega\}\-weakly monotone\.

Lemma[1](https://arxiv.org/html/2606.11804#Thmlemma1)provides the structural foundation for applying DR\-submodular optimization tools to continuous data summarization\. It shows that the proposed continuous objective inherits the diminishing\-returns structure of the underlying discrete summarization utility\. However, once the similarity matrix is perturbed, the resulting objective must be re\-examined to verify whether it remains in the same structural class\. To formalize this, we perturb the similarity matrix entrywise\. Specifically, for each victim model, the perturbed similarity matrix is given bysμ,ν​\(𝐯\)=sμ,ν\+vμ,ν,s\_\{\\mu,\\nu\}\(\\mathbf\{v\}\)=s\_\{\\mu,\\nu\}\+v\_\{\\mu,\\nu\},where the perturbation satisfies

𝐯∈𝒫p​\(ϵp\)=\{𝐯:‖𝐯‖p≤ϵp,0≤sμ,ν\+vμ,ν≤1,∀μ,ν\}\.\\mathbf\{v\}\\in\\mathcal\{P\}\_\{p\}\(\\epsilon\_\{p\}\)=\\left\\\{\\mathbf\{v\}:\\\|\\mathbf\{v\}\\\|\_\{p\}\\leq\\epsilon\_\{p\},\\;0\\leq s\_\{\\mu,\\nu\}\+v\_\{\\mu,\\nu\}\\leq 1,\\ \\forall\\mu,\\nu\\right\\\}\.Thus, all perturbed similarities remain nonnegative and bounded in\[0,1\]\[0,1\]\.

The following lemma clarifies when the perturbed objective preserves the structural properties required by our analysis\.

###### Lemma 2\(Structural preservation under admissible perturbations\)\.

Under the perturbation set𝒫p​\(ϵp\)\\mathcal\{P\}\_\{p\}\(\\epsilon\_\{p\}\), the perturbed similarity matrix remains entrywise nonnegative\. Moreover, if the perturbed discrete utilityf​\(S,Ω​\(𝐯\)\)f\(S,\\Omega\(\\mathbf\{v\}\)\)remains submodular and satisfiesρΩ​\(𝐯\)<1\\rho\_\{\\Omega\(\\mathbf\{v\}\)\}<1, then its multilinear extensionF​\(𝐱,Ω​\(𝐯\)\)F\(\\mathbf\{x\},\\Omega\(\\mathbf\{v\}\)\)is non\-negative, DR\-submodular with respect to𝐱\\mathbf\{x\}, andmΩ​\(𝐯\)m\_\{\\Omega\(\\mathbf\{v\}\)\}\-weakly monotone, wheremΩ​\(𝐯\)=1−ρΩ​\(𝐯\)m\_\{\\Omega\(\\mathbf\{v\}\)\}=1\-\\rho\_\{\\Omega\(\\mathbf\{v\}\)\}\.

Accordingly, the theoretical results in the following sections are stated for perturbations under which the perturbed objective remains within the same non\-negative DR\-submodular and weakly monotone structural class\.

### III\-CThreat Model and Attack Surface

We consider a data\-processing pipeline in which raw data are first converted into feature representations, a similarity structure is then constructed from these representations, and a continuous summarization module selects or weights representative items before the summarized data are used by downstream learning or decision modules\. In this pipeline, the summarization module is an upstream component: it determines which information is retained and therefore can affect the reliability of subsequent tasks\.

#### III\-C1Attack surface

This paper focuses on similarity\-level attacks against the summarization module\. This perturbation model abstracts attacks on the representation or similarity\-construction stage of the summarization pipeline\. As formalized in Sec\.[III\-B](https://arxiv.org/html/2606.11804#S3.SS2), the adversary applies an admissible perturbation𝐯∈𝒫p​\(ϵp\)\\mathbf\{v\}\\in\\mathcal\{P\}\_\{p\}\(\\epsilon\_\{p\}\)to the upstream similarity structure used by the summarization objective, while all perturbed similarities remain valid scores in\[0,1\]\[0,1\]\. Note that the adversary does not directly choose the final summary, modify the summarization decision variable𝐱\\mathbf\{x\}, or edit the rounded summarySk​\(𝐱\)S\_\{k\}\(\\mathbf\{x\}\)\. Instead, the attack affects the summarizer indirectly by changing the objective on which the summary is optimized\. The summarization algorithm is then executed on the perturbed objective, and the resulting summary is evaluated under the original clean objective to measure the quality loss caused by the upstream perturbation\.

#### III\-C2Adversary’s knowledge and capability

We mainly study a white\-box, gradient\-access adversary\. The adversary knows the summarization objective, the feasible set, and the perturbation budget, and can query the target summarization models to obtain function\-value and gradient information\. This setting is used to evaluate worst\-case vulnerability of optimization\-based summarization systems and provides an upper bound on the damage that a structure\-aware adversary may cause\. In the multi\-target setting, the adversary aims to construct a single perturbation that degrades multiple target summarization models simultaneously, rather than generating a separate perturbation for each model\.

#### III\-C3Defender’s knowledge and objective

The defender controls the summarization algorithm and seeks a solution that remains useful under possible perturbations of the similarity structure\. Since the defender may not know in advance which type of perturbation will occur, we consider a mixed\-attack setting\. Each attack typej∈\[J\]j\\in\[J\]is associated with a feasible perturbation set𝒫j\\mathcal\{P\}\_\{j\}\. The defender therefore optimizes the summarization decision against the worst\-case mixture of these perturbations\. The goal is not to eliminate all possible performance loss, but to reduce attack\-induced utility degradation while maintaining high clean\-data summarization quality\.

#### III\-C4Scope and limitations

The proposed threat model is most appropriate for systems in which the similarity matrix, or the representation module used to construct it, is accessible or indirectly manipulable\. We do not assume that every admissible entrywise similarity perturbation can be realized by imperceptible pixel\-level changes to raw inputs\. Instead, the perturbation set provides a controlled abstraction for analyzing how bounded changes to the upstream similarity structure affect the summarization solution and its clean\-objective utility\.

Fig\.[1](https://arxiv.org/html/2606.11804#S3.F1)summarizes the clean summarization pipeline, the similarity\-level attack surface, the defender’s robust protection mechanism, and the downstream evaluation protocol\.

Raw dataΩ\\OmegaFeaturevectorsCleansimilaritySSContinuoussummarizerdecision𝐱\\mathbf\{x\}SelectedsummaryDownstreamtaskWhite\-boxadversaryQueriesvalues/gradientsAdmissibleperturbation𝐯∈𝒫p​\(ϵp\)\\mathbf\{v\}\\in\\mathcal\{P\}\_\{p\}\(\\epsilon\_\{p\}\)PerturbedsimilarityS\+𝐯S\+\\mathbf\{v\}Validity0≤S\+𝐯≤10\\leq S\+\\mathbf\{v\}\\leq 1No direct edit of𝐱\\mathbf\{x\}or summaryMulti\-model setting:one perturbation affectsmultiple target summarizersMixed attacksets\{𝒫j\}j=1J\\\{\\mathcal\{P\}\_\{j\}\\\}\_\{j=1\}^\{J\}Max–minrobust solvermax𝐱⁡min𝐰,𝐯j⁡G\\max\_\{\\mathbf\{x\}\}\\min\_\{\\mathbf\{w\},\\mathbf\{v\}^\{j\}\}GRobustsummary decision𝐱rob\\mathbf\{x\}^\{\\rm rob\}Clean\-objectiveevaluationTask\-levelreliabilityFigure 1:Threat model and attack surface for similarity\-based continuous summarization\. The clean pipeline constructs a similarity matrixSS, optimizes a continuous summarization decision𝐱\\mathbf\{x\}, and passes the selected summary to downstream tasks\. The adversary has white\-box query access and perturbs the upstream similarity structure through an admissible perturbation𝐯∈𝒫p​\(ϵp\)\\mathbf\{v\}\\in\\mathcal\{P\}\_\{p\}\(\\epsilon\_\{p\}\), yieldingS\+𝐯S\+\\mathbf\{v\}, but does not directly edit𝐱\\mathbf\{x\}or the final summary\. The defender solves a max–min robust summarization problem over mixed perturbation sets\{𝒫j\}j=1J\\\{\\mathcal\{P\}\_\{j\}\\\}\_\{j=1\}^\{J\}\. Both summarization utility and downstream task reliability are evaluated to connect optimization\-level degradation with trustworthy\-AI pipeline reliability\.

### III\-DAttack and Defense Formulations

Based on the threat model above, we now formalize the attack and defense problems\. On the attack side, the adversary searches for a bounded perturbation of the similarity structure that causes the summarization algorithm to output lower\-quality solutions under the clean objective\. On the defense side, the model owner seeks a summarization solution that remains stable and useful under mixed perturbation types\.

#### III\-D1Multi\-Target Attack Formulation

Suppose there areIItarget summarization models\. To generate a single perturbation that degrades all target models simultaneously, we consider

min𝐯∈𝒫,t⁡ts\.t\.max𝐱i∈𝒳i⁡Fi​\(𝐯,𝐱i\)≤t,∀i∈\[I\],\\min\_\{\\mathbf\{v\}\\in\\mathcal\{P\},\\,t\}t\\qquad\\text\{s\.t\.\}\\quad\\max\_\{\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\}\}F\_\{i\}\(\\mathbf\{v\},\\mathbf\{x\}^\{i\}\)\\leq t,\\quad\\forall i\\in\[I\],where𝐯∈𝒫\\mathbf\{v\}\\in\\mathcal\{P\}is the perturbation applied to the similarity structure and𝐱i∈𝒳i\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\}is the summarization decision for theii\-th model\. To obtain a tractable formulation, we introduce the weight vector𝐰\\mathbf\{w\}and define the min\-max convex\-submodular problem as

min𝐯∈𝒫⁡max𝐰∈𝒲,𝐱i∈𝒳i⁡ϕ​\(𝐯,𝐰,\{𝐱i\}\),\\min\_\{\\mathbf\{v\}\\in\\mathcal\{P\}\}\\max\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\,\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\}\}\\phi\(\\mathbf\{v\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\),\(3\)whereϕ​\(𝐯,𝐰,\{𝐱i\}\)=∑i=1I𝐰i​Fi​\(𝐯,𝐱i\)\\phi\(\\mathbf\{v\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)=\\sum\_\{i=1\}^\{I\}\\mathbf\{w\}\_\{i\}F\_\{i\}\(\\mathbf\{v\},\\mathbf\{x\}^\{i\}\), and𝒲=\{𝐰\|1T​𝐰=1,𝐰i∈\[0,1\],∀i\}\\mathcal\{W\}=\\left\\\{\\mathbf\{w\}\\ \\middle\|\\ \\mathbf\{1\}^\{T\}\\mathbf\{w\}=1,\\ \\mathbf\{w\}\_\{i\}\\in\[0,1\],\\ \\forall i\\right\\\}\. Here,Fi​\(𝐯,𝐱i\)F\_\{i\}\(\\mathbf\{v\},\\mathbf\{x\}^\{i\}\)denotes the objective value of theii\-th attacked summarization model defined on the perturbed datasetΩi​\(𝐯\)\\Omega\_\{i\}\(\\mathbf\{v\}\)\. We use the following approximation notion for the attack problem\. We say that𝐯¯\\bar\{\\mathbf\{v\}\}is an\(α,ϵ\)\(\\alpha,\\epsilon\)\-approximation min\-max solution of \([3](https://arxiv.org/html/2606.11804#S3.E3)\) if

α​max𝐰∈𝒲,𝐱i∈𝒳i⁡ϕ​\(𝐯¯,𝐰,\{𝐱i\}\)≤OPTminmax\+ϵ,\\alpha\\max\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\,\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\}\}\\phi\(\\bar\{\\mathbf\{v\}\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)\\leq\{\\rm OPT\}\_\{\\rm minmax\}\+\\epsilon,whereOPTminmax=min𝐯∈𝒫⁡max𝐰∈𝒲,𝐱i∈𝒳i⁡ϕ​\(𝐯,𝐰,\{𝐱i\}\)\.\{\\rm OPT\}\_\{\\rm minmax\}=\\min\_\{\\mathbf\{v\}\\in\\mathcal\{P\}\}\\max\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\,\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\}\}\\phi\(\\mathbf\{v\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)\.

#### III\-D2Robust Defense Formulation

We now turn to the defender’s perspective\. Since the model owner may face multiple possible attack types and may not know in advance which one will occur, we seek a robust solution that performs well against mixed attacks\. Let𝐯j∈𝒫j\\mathbf\{v\}^\{j\}\\in\\mathcal\{P\}\_\{j\}denote the perturbation associated with thejj\-th attack type, wherej∈\[J\]j\\in\[J\]\. We then consider the following regularized max\-min submodular\-convex formulation:

max𝐱∈𝒳⁡min𝐰∈𝒲,𝐯j∈𝒫j⁡G​\(𝐱,𝐰,\{𝐯j\}\),\\max\_\{\\mathbf\{x\}\\in\\mathcal\{X\}\}\\min\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\,\\mathbf\{v\}^\{j\}\\in\\mathcal\{P\}\_\{j\}\}G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\),\(4\)where

G​\(𝐱,𝐰,\{𝐯j\}\)\\displaystyle G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)=\\displaystyle=∑j=1Jwj​F​\(𝐱,𝐯j\)\\displaystyle\\sum\_\{j=1\}^\{J\}w\_\{j\}F\(\\mathbf\{x\},\\mathbf\{v\}^\{j\}\)\+λv2​∑j=1J‖𝐯j‖22\+γ2​‖𝐰−1J​𝟏‖22\.\\displaystyle\+\\frac\{\\lambda\_\{v\}\}\{2\}\\sum\_\{j=1\}^\{J\}\\\|\\mathbf\{v\}^\{j\}\\\|\_\{2\}^\{2\}\+\\frac\{\\gamma\}\{2\}\\left\\\|\\mathbf\{w\}\-\\frac\{1\}\{J\}\\mathbf\{1\}\\right\\\|\_\{2\}^\{2\}\.
Here, for perturbations under which the perturbed objective remains in the same structural class,F​\(𝐱,𝐯j\)F\(\\mathbf\{x\},\\mathbf\{v\}^\{j\}\)is non\-negative,mm\-weakly monotone, and DR\-submodular with respect to𝐱\\mathbf\{x\}, while𝐰\\mathbf\{w\}lies in the simplex set

𝒲=\{𝐰\|1T​𝐰=1,wj∈\[0,1\],∀j∈\[J\]\}\.\\mathcal\{W\}=\\left\\\{\\mathbf\{w\}\\ \\middle\|\\ \\mathbf\{1\}^\{T\}\\mathbf\{w\}=1,\\ w\_\{j\}\\in\[0,1\],\\ \\forall j\\in\[J\]\\right\\\}\.The regularization parameterλv\>0\\lambda\_\{v\}\>0is introduced to stabilize the inner minimization with respect to the perturbation variables and to induce strong convexity in𝐯j\\mathbf\{v\}^\{j\}\. The regularization parameterγ\>0\\gamma\>0is introduced to avoid over\-concentration on any single attack type and to promote balanced robustness across mixed attacks\.

We use the following approximation notion for the robust defense problem\. We say that𝐱¯\\bar\{\\mathbf\{x\}\}is a\(β,ϵ\)\(\\beta,\\epsilon\)\-approximation max\-min solution of \([4](https://arxiv.org/html/2606.11804#S3.E4)\) if

min𝐰∈𝒲,𝐯j∈𝒫j⁡G​\(𝐱¯,𝐰,\{𝐯j\}\)≥β​OPTmaxmin−ϵ,\\min\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\,\\mathbf\{v\}^\{j\}\\in\\mathcal\{P\}\_\{j\}\}G\(\\bar\{\\mathbf\{x\}\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)\\geq\\beta\\,\{\\rm OPT\}\_\{\\rm maxmin\}\-\\epsilon,whereOPTmaxmin=max𝐱∈𝒳⁡min𝐰∈𝒲,𝐯j∈𝒫j⁡G​\(𝐱,𝐰,\{𝐯j\}\)\{\\rm OPT\}\_\{\\rm maxmin\}=\\max\_\{\\mathbf\{x\}\\in\\mathcal\{X\}\}\\min\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\,\\mathbf\{v\}^\{j\}\\in\\mathcal\{P\}\_\{j\}\}G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)\.

## IVAdversarial Attack Generation against Multiple Summarization Models

In this section, we study multi\-target adversarial attack generation for continuous summarization models, with the goal of characterizing adversarial vulnerability in an upstream data summarization component of trustworthy AI pipelines\. We first present a greedy maximization subroutine formm\-weakly monotone DR\-submodular objectives, and then build a multi\-target attack algorithm on top of it\. Detailed proofs are deferred to the Appendix\.

### IV\-AGreedy Maximization Subroutine

For a fixed perturbation𝐯\\mathbf\{v\}, we consider the problem

max𝐱∈𝒳⁡F​\(𝐯,𝐱\),\\max\_\{\\mathbf\{x\}\\in\\mathcal\{X\}\}F\(\\mathbf\{v\},\\mathbf\{x\}\),where𝒳\\mathcal\{X\}is a down\-closed convex set with diameterDD\. To solve this problem, we introduce a continuous greedy\-type procedure, denoted byℳgreedy\\mathcal\{M\}\_\{\\rm greedy\}\. SinceF​\(𝐯,𝐱\)F\(\\mathbf\{v\},\\mathbf\{x\}\)is onlymm\-weakly monotone rather than fully monotone, negative gradient coordinates may decrease the objective value\. We therefore use the clipped gradient

g​\(𝐱t\):=∇𝐱F​\(𝐯,𝐱t\)∨𝟎,g\(\\mathbf\{x\}\_\{t\}\):=\\nabla\_\{\\mathbf\{x\}\}F\(\\mathbf\{v\},\\mathbf\{x\}\_\{t\}\)\\vee\\mathbf\{0\},which removes descent directions\. As a result, the update direction only keeps coordinates corresponding to nonnegative partial derivatives, and the following identity holds:

⟨∇𝐱F​\(𝐯,𝐱t\),𝐱t\+1−𝐱t⟩=⟨g​\(𝐱t\),𝐱t\+1−𝐱t⟩\.\\left\\langle\\nabla\_\{\\mathbf\{x\}\}F\(\\mathbf\{v\},\\mathbf\{x\}\_\{t\}\),\\mathbf\{x\}\_\{t\+1\}\-\\mathbf\{x\}\_\{t\}\\right\\rangle=\\left\\langle g\(\\mathbf\{x\}\_\{t\}\),\\mathbf\{x\}\_\{t\+1\}\-\\mathbf\{x\}\_\{t\}\\right\\rangle\.\(5\)This relation is central to the approximation analysis\.

Algorithm 1General Continuous Greedy Algorithmℳgreedy\\mathcal\{M\}\_\{\\rm greedy\}0:

F​\(𝐯,𝐱\),𝒳,TF\(\\mathbf\{v\},\\mathbf\{x\}\),\\mathcal\{X\},T, and

𝐱0=𝟎\\mathbf\{x\}\_\{0\}=\\mathbf\{0\}
1:for

t=0,…,T−1t=0,\\ldots,T\-1do

2:Compute

𝐝¯t=arg⁡max𝐝∈𝒳⁡⟨g​\(𝐱t\),𝐝⟩,g​\(𝐱t\)=∇𝐱F​\(𝐯,𝐱t\)∨𝟎\\bar\{\\mathbf\{d\}\}\_\{t\}=\\arg\\max\_\{\\mathbf\{d\}\\in\\mathcal\{X\}\}\\langle g\(\\mathbf\{x\}\_\{t\}\),\\mathbf\{d\}\\rangle,\\qquad g\(\\mathbf\{x\}\_\{t\}\)=\\nabla\_\{\\mathbf\{x\}\}F\(\\mathbf\{v\},\\mathbf\{x\}\_\{t\}\)\\vee\\mathbf\{0\}
3:Direction clipping:

\[𝐝t\]s=\{\[𝐝¯t\]s,s∈\{s:\[∇F​\(𝐯,𝐱t\)\]s≥0\},0,otherwise\[\\mathbf\{d\}\_\{t\}\]\_\{s\}=\\begin\{cases\}\[\\bar\{\\mathbf\{d\}\}\_\{t\}\]\_\{s\},&s\\in\\\{s:\[\\nabla F\(\\mathbf\{v\},\\mathbf\{x\}\_\{t\}\)\]\_\{s\}\\geq 0\\\},\\\\ 0,&\\text\{otherwise\}\\end\{cases\}
4:

𝐱t\+1=𝐱t\+1T​𝐝t\\mathbf\{x\}\_\{t\+1\}=\\mathbf\{x\}\_\{t\}\+\\frac\{1\}\{T\}\\mathbf\{d\}\_\{t\}
5:endfor

6:Return

𝐱T\\mathbf\{x\}\_\{T\}

We can now state the approximation guarantee ofℳgreedy\\mathcal\{M\}\_\{\\rm greedy\}\.

###### Theorem 1\(Proof in Sec\.[\-B](https://arxiv.org/html/2606.11804#A0.SS2)\)\.

LetF​\(𝐯,𝐱\)F\(\\mathbf\{v\},\\mathbf\{x\}\)be a nonnegative,LL\-smooth, DR\-submodular function that is alsomm\-weakly monotone\. Then the output𝐱T\\mathbf\{x\}\_\{T\}of Alg\.[1](https://arxiv.org/html/2606.11804#alg1)satisfies

F​\(𝐯,𝐱T\)≥m​\(1−1/e\)​max𝐱∈𝒳⁡F​\(𝐯,𝐱\)−ϵF\(\\mathbf\{v\},\\mathbf\{x\}\_\{T\}\)\\geq m\(1\-1/e\)\\max\_\{\\mathbf\{x\}\\in\\mathcal\{X\}\}F\(\\mathbf\{v\},\\mathbf\{x\}\)\-\\epsilonafter𝒪​\(L​D2/ϵ\)\\mathcal\{O\}\(LD^\{2\}/\\epsilon\)iterations\.

Assuming the availability of gradient evaluations and a linear maximization oracle \(LMO\), we obtain the following oracle complexity\.

###### Corollary 1\(Oracle complexity ofℳgreedy\\mathcal\{M\}\_\{\\rm greedy\}\)\.

Under the same assumptions as Theorem[1](https://arxiv.org/html/2606.11804#Thmtheorem1), Alg\.[1](https://arxiv.org/html/2606.11804#alg1)achieves an\(m​\(1−e−1\),ϵ\)\(m\(1\-e^\{\-1\}\),\\epsilon\)\-approximation using𝒪​\(ϵ−1\)\\mathcal\{O\}\(\\epsilon^\{\-1\}\)gradient evaluations and𝒪​\(ϵ−1\)\\mathcal\{O\}\(\\epsilon^\{\-1\}\)LMO calls\.

### IV\-BMulti\-Target Attack Algorithm

We now build a multi\-target attack algorithm on top ofℳgreedy\\mathcal\{M\}\_\{\\rm greedy\}\. At each outer iteration, the algorithm approximately solves the inner maximization over\{𝐱i\}\\\{\\mathbf\{x\}^\{i\}\\\}usingℳgreedy\\mathcal\{M\}\_\{\\rm greedy\}, updates the model weights𝐰\\mathbf\{w\}by maximizing the current aggregated objective, and then performs a projected gradient step on the perturbation variable𝐯\\mathbf\{v\}\.

Algorithm 2Minmax Convex\-Submodular Approximation Algorithm0:

𝐯0,𝐰0\\mathbf\{v\}\_\{0\},\\mathbf\{w\}\_\{0\}, iteration number

KK, subroutine

ℳgreedy\\mathcal\{M\}\_\{\\rm greedy\}, and constraint sets

𝒫,𝒲,𝒳i\\mathcal\{P\},\\mathcal\{W\},\\mathcal\{X\}\_\{i\}
1:for

k=0,…,K−1k=0,\\ldots,K\-1do

2:For

i=1,…,Ii=1,\\ldots,I, run

𝐱k\+1i=ℳgreedy​\(Fi​\(𝐯k,𝐱i\),𝒳i,T\)\\mathbf\{x\}^\{i\}\_\{k\+1\}=\\mathcal\{M\}\_\{\\rm greedy\}\(F\_\{i\}\(\\mathbf\{v\}\_\{k\},\\mathbf\{x\}^\{i\}\),\\mathcal\{X\}\_\{i\},T\)
3:Update

𝐰k\+1=arg⁡max𝐰∈𝒲⁡ϕ​\(𝐯k,𝐰,\{𝐱k\+1i\}\)\\mathbf\{w\}\_\{k\+1\}=\\arg\\max\_\{\\mathbf\{w\}\\in\\mathcal\{W\}\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\_\{k\+1\}\\\}\)
4:Update

𝐯k\+1=proj𝒫​\(𝐯k−η​∇𝐯ϕ​\(𝐯k,𝐰k\+1,\{𝐱k\+1i\}\)\)\\mathbf\{v\}\_\{k\+1\}=\{\\rm proj\}\_\{\\mathcal\{P\}\}\\Bigl\(\\mathbf\{v\}\_\{k\}\-\\eta\\nabla\_\{\\mathbf\{v\}\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\+1\},\\\{\\mathbf\{x\}^\{i\}\_\{k\+1\}\\\}\)\\Bigr\)
5:endfor

6:Return

𝐯¯=1K​∑k=1K𝐯k\\bar\{\\mathbf\{v\}\}=\\frac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}\\mathbf\{v\}\_\{k\}

For each iterate𝐯k\\mathbf\{v\}\_\{k\}, Alg\.[2](https://arxiv.org/html/2606.11804#alg2)first computes approximate maximizers\{𝐱k\+1i\}\\\{\\mathbf\{x\}^\{i\}\_\{k\+1\}\\\}for all target models, then updates the weight vector𝐰k\+1\\mathbf\{w\}\_\{k\+1\}to emphasize the currently worst\-performing models, and finally updates the perturbation variable𝐯k\+1\\mathbf\{v\}\_\{k\+1\}by a projected gradient step over𝒫\\mathcal\{P\}\. Here the Euclidean projection operator is defined by

proj𝒫​\(𝐚\)=arg⁡min𝐱∈𝒫⁡‖𝐱−𝐚‖22\.\{\\rm proj\}\_\{\\mathcal\{P\}\}\(\\mathbf\{a\}\)=\\arg\\min\_\{\\mathbf\{x\}\\in\\mathcal\{P\}\}\\\|\\mathbf\{x\}\-\\mathbf\{a\}\\\|\_\{2\}^\{2\}\.
We impose the following regularity conditions for the attack analysis\.

###### Assumption 1\.

For each target model,Fi​\(𝐯,𝐱i\)F\_\{i\}\(\\mathbf\{v\},\\mathbf\{x\}^\{i\}\)is differentiable,MM\-Lipschitz continuous in\(𝐯,𝐱i\)\(\\mathbf\{v\},\\mathbf\{x\}^\{i\}\),LL\-smooth with respect to𝐱i\\mathbf\{x\}^\{i\}, and convex with respect to𝐯\\mathbf\{v\}\. Moreover, each𝒳i\\mathcal\{X\}\_\{i\}is a down\-closed convex set with diameterD𝒳iD\_\{\\mathcal\{X\}\_\{i\}\}, and𝒫\\mathcal\{P\}is a compact convex set with diameterD𝒫D\_\{\\mathcal\{P\}\}\.

### IV\-CApproximation Guarantee and Oracle Complexity

The following guarantee is conditional on convexity of the attacked objective with respect to the variable𝐯\\mathbf\{v\}for Alg\.[2](https://arxiv.org/html/2606.11804#alg2)\.

###### Theorem 2\(Proof in Sec\.[\-B](https://arxiv.org/html/2606.11804#A0.SS2)\)\.

For adversarial sample generation across multiple smooth DR\-submodular maximization models that aremm\-weakly monotone, under Assumption[1](https://arxiv.org/html/2606.11804#Thmassumption1)and withη=1/K\\eta=1/\\sqrt\{K\}, the output𝐯¯\\bar\{\\mathbf\{v\}\}of Alg\.[2](https://arxiv.org/html/2606.11804#alg2)with subroutineℳgreedy\\mathcal\{M\}\_\{\\rm greedy\}satisfies

m​\(1−1/e\)​max𝐰∈𝒲,𝐱i∈𝒳i⁡ϕ​\(𝐯¯,𝐰,\{𝐱i\}\)≤OPTminmax\+ϵm\(1\-1/e\)\\max\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\,\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\}\}\\phi\(\\bar\{\\mathbf\{v\}\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)\\leq\{\\rm OPT\}\_\{\\rm minmax\}\+\\epsilonafter𝒪​\(D𝒫/ϵ2\)\\mathcal\{O\}\(D\_\{\\mathcal\{P\}\}/\\epsilon^\{2\}\)outer iterations in Alg\.[2](https://arxiv.org/html/2606.11804#alg2)and𝒪​\(L​D2/ϵ\)\\mathcal\{O\}\(LD^\{2\}/\\epsilon\)inner iterations inℳgreedy\\mathcal\{M\}\_\{\\rm greedy\}\.

Assuming the availability of gradient evaluations, an LMO, and a projection oracle over convex sets, we obtain the following complexity bound\.

###### Corollary 2\(Oracle complexity\)\.

Under the same conditions as Theorem[2](https://arxiv.org/html/2606.11804#Thmtheorem2), Alg\.[2](https://arxiv.org/html/2606.11804#alg2)achieves an\(m​\(1−1/e\),ϵ\)\(m\(1\-1/e\),\\epsilon\)\-approximation min\-max solution with𝒪​\(I​ϵ−3\+ϵ−2\)\\mathcal\{O\}\(I\\epsilon^\{\-3\}\+\\epsilon^\{\-2\}\)gradient evaluations,𝒪​\(I​ϵ−3\+ϵ−2\)\\mathcal\{O\}\(I\\epsilon^\{\-3\}\+\\epsilon^\{\-2\}\)LMO calls, and𝒪​\(ϵ−2\)\\mathcal\{O\}\(\\epsilon^\{\-2\}\)projection\-oracle calls\.

The guarantee simplifies in the single\-model monotone case\.

### IV\-DProof Sketch

The guarantee of Theorem[2](https://arxiv.org/html/2606.11804#Thmtheorem2)follows from combining an approximate inner maximization step with a projected outer update on the perturbation variable\. First, by Theorem[1](https://arxiv.org/html/2606.11804#Thmtheorem1), the subroutineℳgreedy\\mathcal\{M\}\_\{\\rm greedy\}provides anm​\(1−1/e\)m\(1\-1/e\)\-approximate solution for each inner DR\-submodular maximization problem\. Second, the projected gradient update on𝐯\\mathbf\{v\}yields a descent\-type inequality for the min\-max objective through the convexity ofϕ​\(⋅,𝐰,\{𝐱i\}\)\\phi\(\\cdot,\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)and the projection step\.

Specifically, the gradient ofϕ\\phiwith respect to𝐯\\mathbf\{v\}is

∇𝐯ϕ​\(𝐯,𝐰,\{𝐱i\}\)=∑i=1I𝐰i​∇𝐯Fi​\(𝐯,𝐱i\),\\nabla\_\{\\mathbf\{v\}\}\\phi\(\\mathbf\{v\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)=\\sum\_\{i=1\}^\{I\}\\mathbf\{w\}\_\{i\}\\nabla\_\{\\mathbf\{v\}\}F\_\{i\}\(\\mathbf\{v\},\\mathbf\{x\}^\{i\}\),and Assumption[1](https://arxiv.org/html/2606.11804#Thmassumption1)implies the bound

‖∇𝐯ϕ​\(𝐯,𝐰,\{𝐱i\}\)‖2≤M2,∀𝐰∈𝒲\.\\\|\\nabla\_\{\\mathbf\{v\}\}\\phi\(\\mathbf\{v\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)\\\|^\{2\}\\leq M^\{2\},\\qquad\\forall\\,\\mathbf\{w\}\\in\\mathcal\{W\}\.\(6\)
To quantify one\-step progress, define

τ𝐯=ϕ​\(𝐯,𝐰k\+1,\{𝐱k\+1i\}\)−ϕ​\(𝐯k,𝐰k\+1,\{𝐱k\+1i\}\)\.\\tau\_\{\\mathbf\{v\}\}=\\phi\(\\mathbf\{v\},\\mathbf\{w\}\_\{k\+1\},\\\{\\mathbf\{x\}^\{i\}\_\{k\+1\}\\\}\)\-\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\+1\},\\\{\\mathbf\{x\}^\{i\}\_\{k\+1\}\\\}\)\.The key step is the following inequality\.

###### Lemma 3\.

Under Assumption[1](https://arxiv.org/html/2606.11804#Thmassumption1),

τ𝐯≥‖𝐯k\+1−𝐯‖2−‖𝐯k−𝐯‖22​η−η​M22\.\\tau\_\{\\mathbf\{v\}\}\\geq\\frac\{\\\|\\mathbf\{v\}\_\{k\+1\}\-\\mathbf\{v\}\\\|^\{2\}\-\\\|\\mathbf\{v\}\_\{k\}\-\\mathbf\{v\}\\\|^\{2\}\}\{2\\eta\}\-\\frac\{\\eta M^\{2\}\}\{2\}\.\(7\)

Summing \([7](https://arxiv.org/html/2606.11804#S4.E7)\) over the outer iterations, combining it with the approximation guarantee ofℳgreedy\\mathcal\{M\}\_\{\\rm greedy\}for the inner maximization, and then using the convexity ofϕ​\(⋅,𝐰,\{𝐱i\}\)\\phi\(\\cdot,\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)yields Theorem[2](https://arxiv.org/html/2606.11804#Thmtheorem2)\. The full proofs of Lemma[3](https://arxiv.org/html/2606.11804#Thmlemma3)and Theorem[2](https://arxiv.org/html/2606.11804#Thmtheorem2)are deferred to the Appendix\.

## VRobust Defense under Mixed Attacks

In this section, we study robust protection against adversarial perturbations in continuous data summarization under mixed attack types\. Our goal is to compute a summarization solution that preserves utility while remaining stable against multiple possible attack constraints\. We formulate this protection task as a robust submodular maximization problem and develop a corresponding approximation algorithm\. Detailed proofs are deferred to the Appendix\.

### V\-ARobust Continuous Greedy Algorithm

We propose a robust continuous greedy algorithm for maximizing anmm\-weakly monotone DR\-submodular objective under mixed attacks\. At each outer iteration, the algorithm performs three steps: it first approximately updates each adversarial variable𝐯j\\mathbf\{v\}^\{j\}by projected gradient descent, then computes the worst\-case mixture weights𝐰\\mathbf\{w\}by solving the inner minimization over𝒲\\mathcal\{W\}, and finally updates the primal variable𝐱\\mathbf\{x\}through a clipped\-gradient continuous greedy step\.

More specifically, for a fixed iterate𝐱k\\mathbf\{x\}\_\{k\}, we compute𝐯Tj​\(𝐱k\)\\mathbf\{v\}^\{j\}\_\{T\}\(\\mathbf\{x\}\_\{k\}\)by projected gradient descent onG​\(𝐱k,𝐰,⋅\)G\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\},\\cdot\)for each attack typej∈\[J\]j\\in\[J\], the gradient with respect to𝐯j\\mathbf\{v\}^\{j\}is

∇𝐯jG=wt,j​∇𝐯jF​\(𝐱k,𝐯tj\)\+λ𝐯​𝐯tj\.\\nabla\_\{\\mathbf\{v\}^\{j\}\}G=w\_\{t,j\}\\nabla\_\{\\mathbf\{v\}^\{j\}\}F\(\\mathbf\{x\}\_\{k\},\\mathbf\{v\}^\{j\}\_\{t\}\)\+\\lambda\_\{\\mathbf\{v\}\}\\mathbf\{v\}^\{j\}\_\{t\}\.and define

𝐰∗​\(\{𝐯Tj\}k\)=arg⁡min𝐰∈𝒲⁡G​\(𝐱k,𝐰,\{𝐯Tj​\(𝐱k\)\}\)\.\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\)=\\arg\\min\_\{\\mathbf\{w\}\\in\\mathcal\{W\}\}G\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\_\{T\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)\.We then use the clipped gradient

\[∇𝐱G​\(𝐱k\)\]\+=∇𝐱G​\(𝐱k,𝐰∗​\(\{𝐯Tj\}k\),\{𝐯Tj​\(𝐱k\)\}\)∨𝟎,\[\\nabla\_\{\\mathbf\{x\}\}G\(\\mathbf\{x\}\_\{k\}\)\]\_\{\+\}=\\nabla\_\{\\mathbf\{x\}\}G\\\!\\left\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\),\\\{\\mathbf\{v\}^\{j\}\_\{T\}\(\\mathbf\{x\}\_\{k\}\)\\\}\\right\)\\vee\\mathbf\{0\},to define the ascent direction\. As in the attack\-side greedy routine, clipping removes directions corresponding to negative gradients\. Consequently,

⟨∇𝐱G​\(𝐱k,𝐰∗​\(\{𝐯Tj\}k\),\{𝐯Tj​\(𝐱k\)\}\),𝐝k⟩=⟨\[∇𝐱G​\(𝐱k\)\]\+,𝐝k⟩\.\\left\\langle\\nabla\_\{\\mathbf\{x\}\}G\\\!\\left\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\),\\\{\\mathbf\{v\}^\{j\}\_\{T\}\(\\mathbf\{x\}\_\{k\}\)\\\}\\right\),\\mathbf\{d\}\_\{k\}\\right\\rangle=\\left\\langle\[\\nabla\_\{\\mathbf\{x\}\}G\(\\mathbf\{x\}\_\{k\}\)\]\_\{\+\},\\mathbf\{d\}\_\{k\}\\right\\rangle\.\(8\)
The complete procedure is given below\.

Algorithm 3Robust Continuous Greedy Algorithm0:

𝐯0,𝐰0,η,K,T,𝒫j,𝒳\\mathbf\{v\}\_\{0\},\\mathbf\{w\}\_\{0\},\\eta,K,T,\\mathcal\{P\}\_\{j\},\\mathcal\{X\}
1:for

k=0,…,K−1k=0,\\ldots,K\-1do

2:Initialize

𝐰0​\(𝐯k\)=𝐰0\\mathbf\{w\}\_\{0\}\(\\mathbf\{v\}\_\{k\}\)=\\mathbf\{w\}\_\{0\}
3:for

t=0,…,T−1t=0,\\ldots,T\-1do

4:For each

j∈\[J\]j\\in\[J\], compute

𝐯t\+1j​\(𝐱k\)\\displaystyle\\mathbf\{v\}^\{j\}\_\{t\+1\}\(\\mathbf\{x\}\_\{k\}\)=\\displaystyle=proj𝒫j\(𝐯tj\(𝐱k\)\\displaystyle\{\\rm proj\}\_\{\\mathcal\{P\}\_\{j\}\}\\left\(\\mathbf\{v\}^\{j\}\_\{t\}\(\\mathbf\{x\}\_\{k\}\)\\right\.−η∇𝐯jG\(𝐱k,𝐰t,\{𝐯tℓ\(𝐱k\)\}ℓ=1J\)\)\.\\displaystyle\-\\left\.\\eta\\nabla\_\{\\mathbf\{v\}^\{j\}\}G\\left\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}\_\{t\},\\\{\\mathbf\{v\}^\{\\ell\}\_\{t\}\(\\mathbf\{x\}\_\{k\}\)\\\}\_\{\\ell=1\}^\{J\}\\right\)\\right\)\.
5:endfor

6:Compute

𝐰∗​\(\{𝐯Tj\}k\)=arg⁡min𝐰∈𝒲⁡G​\(𝐱k,𝐰,\{𝐯Tj​\(𝐱k\)\}\)\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\)=\\arg\\min\_\{\\mathbf\{w\}\\in\\mathcal\{W\}\}G\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\_\{T\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)and

𝐝¯k=arg⁡max𝐝∈𝒳⁡⟨\[∇𝐱G​\(𝐱k\)\]\+,𝐝⟩\\bar\{\\mathbf\{d\}\}\_\{k\}=\\arg\\max\_\{\\mathbf\{d\}\\in\\mathcal\{X\}\}\\left\\langle\[\\nabla\_\{\\mathbf\{x\}\}G\(\\mathbf\{x\}\_\{k\}\)\]\_\{\+\},\\mathbf\{d\}\\right\\rangle
7:Direction clipping:

\[𝐝k\]s=\{\[𝐝¯k\]s,s∈𝒮,0,otherwise,\[\\mathbf\{d\}\_\{k\}\]\_\{s\}=\\begin\{cases\}\[\\bar\{\\mathbf\{d\}\}\_\{k\}\]\_\{s\},&s\\in\\mathcal\{S\},\\\\ 0,&\\text\{otherwise\},\\end\{cases\}where

𝒮=\{s:\[∇𝐱G​\(𝐱k,𝐰∗​\(\{𝐯Tj\}k\),\{𝐯Tj​\(𝐱k\)\}\)\]s≥0\}\\mathcal\{S\}=\\left\\\{s:\\left\[\\nabla\_\{\\mathbf\{x\}\}G\\\!\\left\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\),\\\{\\mathbf\{v\}^\{j\}\_\{T\}\(\\mathbf\{x\}\_\{k\}\)\\\}\\right\)\\right\]\_\{s\}\\geq 0\\right\\\}
8:Set

𝐱k\+1=𝐱k\+1K​𝐝k\\mathbf\{x\}\_\{k\+1\}=\\mathbf\{x\}\_\{k\}\+\\frac\{1\}\{K\}\\mathbf\{d\}\_\{k\}
9:endfor

10:Return

𝐱K\\mathbf\{x\}\_\{K\}

We impose the following regularity conditions for the robust defense analysis\.

###### Assumption 2\.

Consider the regularized robust model \([4](https://arxiv.org/html/2606.11804#S3.E4)\)\. For perturbations under which the perturbed objective remains in the same structural class, each functionF​\(𝐱,𝐯j\)F\(\\mathbf\{x\},\\mathbf\{v\}^\{j\}\)is non\-negative,mm\-weakly monotone, and DR\-submodular with respect to𝐱\\mathbf\{x\}, and is jointlyLL\-smooth with respect to\(𝐱,𝐯j\)\(\\mathbf\{x\},\\mathbf\{v\}^\{j\}\)\. Moreover, each perturbation set𝒫j\\mathcal\{P\}\_\{j\}is compact and convex, and𝒳⊆ℝ\+n\\mathcal\{X\}\\subseteq\\mathbb\{R\}\_\{\+\}^\{n\}is a down\-closed convex set with diameterD𝒳D\_\{\\mathcal\{X\}\}\.

For each fixed𝐱\\mathbf\{x\}and𝐰\\mathbf\{w\}, the inner objective

∑j=1Jwj​F​\(𝐱,𝐯j\)\+λv2​∑j=1J‖𝐯j‖22\\sum\_\{j=1\}^\{J\}w\_\{j\}F\(\\mathbf\{x\},\\mathbf\{v\}^\{j\}\)\+\\frac\{\\lambda\_\{v\}\}\{2\}\\sum\_\{j=1\}^\{J\}\\\|\\mathbf\{v\}^\{j\}\\\|\_\{2\}^\{2\}isμ\\mu\-strongly convex with respect to\{𝐯j\}j=1J\\\{\\mathbf\{v\}^\{j\}\\\}\_\{j=1\}^\{J\}, where the strong convexity is induced by the quadratic regularization term\.

Under Assumption[2](https://arxiv.org/html/2606.11804#Thmassumption2), we can establish the following approximation guarantee and oracle complexity for Alg\.[3](https://arxiv.org/html/2606.11804#alg3)\.

### V\-BApproximation Guarantee and Oracle Complexity

We now state the main guarantee of Alg\.[3](https://arxiv.org/html/2606.11804#alg3)\.

###### Theorem 3\(Proof in Appendix\)\.

Under Assumption[2](https://arxiv.org/html/2606.11804#Thmassumption2), let the inner projected\-gradient step size beη=1/L\\eta=1/Land defineρ=1−μ/L≤1\\rho=1\-\\mu/L\\leq 1\. For anyϵ∈\(0,1\)\\epsilon\\in\(0,1\), if

K≥𝒪​\(ϵ−1\)andT≥𝒪​\(logρ⁡\(ϵ−1\)\),K\\geq\\mathcal\{O\}\(\\epsilon^\{\-1\}\)\\qquad\\text\{and\}\\qquad T\\geq\\mathcal\{O\}\(\\log\_\{\\rho\}\(\\epsilon^\{\-1\}\)\),then the output𝐱K\\mathbf\{x\}\_\{K\}of Alg\.[3](https://arxiv.org/html/2606.11804#alg3)is an\(m​\(1−1/e\),ϵ\)\\left\(m\(1\-1/e\),\\epsilon\\right\)\-approximation max\-min solution to \([4](https://arxiv.org/html/2606.11804#S3.E4)\)\. In particular,

min𝐰∈𝒲,𝐯j∈𝒫j⁡G​\(𝐱K,𝐰,\{𝐯j\}\)≥m​\(1−1/e\)​OPTmaxmin−ϵ,\\min\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\,\\mathbf\{v\}^\{j\}\\in\\mathcal\{P\}\_\{j\}\}G\(\\mathbf\{x\}\_\{K\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)\\geq m\(1\-1/e\)\\,\{\\rm OPT\}\_\{\\rm maxmin\}\-\\epsilon,whereOPTmaxmin=max𝐱∈𝒳⁡min𝐰∈𝒲,𝐯j∈𝒫j⁡G​\(𝐱,𝐰,\{𝐯j\}\)\.\{\\rm OPT\}\_\{\\rm maxmin\}=\\max\_\{\\mathbf\{x\}\\in\\mathcal\{X\}\}\\min\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\,\\mathbf\{v\}^\{j\}\\in\\mathcal\{P\}\_\{j\}\}G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)\.

Assuming the availability of gradient evaluations, an LMO, and a projection oracle over convex sets, we obtain the following complexity bound\.

###### Corollary 3\(Oracle complexity\)\.

Under the same conditions as Theorem[3](https://arxiv.org/html/2606.11804#Thmtheorem3), Alg\.[3](https://arxiv.org/html/2606.11804#alg3)produces an\(m​\(1−1/e\),ϵ\)\(m\(1\-1/e\),\\epsilon\)\-approximation max\-min solution using

𝒪​\(J​ϵ−1​logρ⁡ϵ−1\+ϵ−1\)\\mathcal\{O\}\\\!\\left\(J\\epsilon^\{\-1\}\\log\_\{\\rho\}\\epsilon^\{\-1\}\+\\epsilon^\{\-1\}\\right\)gradient evaluations,𝒪​\(ϵ−1\)\\mathcal\{O\}\(\\epsilon^\{\-1\}\)LMO calls, and

𝒪​\(J​ϵ−1​logρ⁡ϵ−1\+ϵ−1\)\\mathcal\{O\}\\\!\\left\(J\\epsilon^\{\-1\}\\log\_\{\\rho\}\\epsilon^\{\-1\}\+\\epsilon^\{\-1\}\\right\)projection\-oracle calls\.

### V\-CProof Sketch

We briefly outline why Alg\.[3](https://arxiv.org/html/2606.11804#alg3)achieves a robust approximation guarantee under mixed attacks\.

First, under Assumption[2](https://arxiv.org/html/2606.11804#Thmassumption2), the inner projected\-gradient updates on𝐯j\\mathbf\{v\}^\{j\}contract toward the corresponding minimizers of the regularized inner problem\. In particular, ifρ=1−μ/L\\rho=1\-\\mu/L, then

‖𝐯Tj​\(𝐱k\)−𝐯j∗​\(𝐱k\)‖≤ρT/2​D𝒫j\.\\\|\\mathbf\{v\}^\{j\}\_\{T\}\(\\mathbf\{x\}\_\{k\}\)\-\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\)\\\|\\leq\\rho^\{T/2\}D\_\{\\mathcal\{P\}\_\{j\}\}\.Second, define the value function

Φ​\(𝐱\):=min𝐰∈𝒲,𝐯j∈𝒫j⁡G​\(𝐱,𝐰,\{𝐯j\}\)\.\\Phi\(\\mathbf\{x\}\):=\\min\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\,\\mathbf\{v\}^\{j\}\\in\\mathcal\{P\}\_\{j\}\}G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)\.\(9\)Using standard sensitivity arguments for strongly convex inner problems, one can show thatΦ\\Phiis smooth and that the minimizer𝐰∗\\mathbf\{w\}^\{\*\}varies Lipschitz\-continuously with the adversarial variables\. Third, the continuous greedy update on𝐱\\mathbf\{x\}yields a one\-step improvement inequality of the form

Φ​\(𝐱k\+1\)−Φ​\(𝐱k\)\\displaystyle\\Phi\(\\mathbf\{x\}\_\{k\+1\}\)\-\\Phi\(\\mathbf\{x\}\_\{k\}\)≥1K​\(m​Φ​\(𝐱∗\)−Φ​\(𝐱k\)−2​D𝒳​‖Δk‖−LΦ2​K​D𝒳2\),\\displaystyle\\geq\\frac\{1\}\{K\}\\left\(m\\Phi\(\\mathbf\{x\}^\{\*\}\)\-\\Phi\(\\mathbf\{x\}\_\{k\}\)\-2D\_\{\\mathcal\{X\}\}\\\|\\Delta\_\{k\}\\\|\-\\frac\{L\_\{\\Phi\}\}\{2K\}D\_\{\\mathcal\{X\}\}^\{2\}\\right\),whereΔk=∇Φ​\(𝐱k\)−∇𝐱G​\(𝐱k,𝐰∗​\(\{𝐯Tj\}k\),\{𝐯Tj​\(𝐱k\)\}\)\\Delta\_\{k\}=\\nabla\\Phi\(\\mathbf\{x\}\_\{k\}\)\-\\nabla\_\{\\mathbf\{x\}\}G\\\!\\left\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\),\\\{\\mathbf\{v\}^\{j\}\_\{T\}\(\\mathbf\{x\}\_\{k\}\)\\\}\\right\)\. Bounding‖Δk‖\\\|\\Delta\_\{k\}\\\|by the contraction error of the inner𝐯j\\mathbf\{v\}^\{j\}\-updates and telescoping the above inequality overk=0,…,K−1k=0,\\dots,K\-1yields Theorem[3](https://arxiv.org/html/2606.11804#Thmtheorem3)\. The detailed proofs of the auxiliary lemmas and the complete proof of Theorem[3](https://arxiv.org/html/2606.11804#Thmtheorem3)are deferred to the Appendix\.

## VIExperimental Evaluation

We organize the experimental evaluation around two complementary theory\-aligned settings\. First, we evaluate the proposed attack and defense algorithms on the multilinear\-extension summarization model constructed from real image datasets, which is directly consistent with the DR\-submodular analysis in Sec\.[IV](https://arxiv.org/html/2606.11804#S4)and Sec\.[V](https://arxiv.org/html/2606.11804#S5)\. Second, we introduce a controlled clustered multi\-target benchmark to isolate the attack\-defense mechanism under a known representative structure\. The first setting is used to evaluate utility degradation and robustness on real data, while the second is used to verify whether a single shared perturbation can consistently disrupt representative selection across multiple related victim models\. For completeness, additional empirical results on the direct continuous\-score objective are reported in Appendix[\-E](https://arxiv.org/html/2606.11804#A0.SS5), since that objective is not the primary model covered by our theoretical guarantees\.

### VI\-AExperimental Setup

#### VI\-A1Real\-data multilinear\-extension summarization

We conduct experiments on CIFAR\-10\[[2](https://arxiv.org/html/2606.11804#bib.bib20)\], MNIST\[[10](https://arxiv.org/html/2606.11804#bib.bib11)\], and Fashion\-MNIST\[[27](https://arxiv.org/html/2606.11804#bib.bib12)\]\. Unless otherwise specified, the main numerical results are reported on CIFAR\-10, while MNIST and Fashion\-MNIST are used for additional validation\. In each experiment, we constructI=10I=10victim summarization models, and each model containsn=50n=50images sampled from the raw dataset\. To evaluate the effect of model size, we also report additional results forn∈\{100,200\}n\\in\\\{100,200\\\}in the Appendix\.

#### VI\-A2Controlled clustered multi\-target benchmark

To further isolate the attack\-defense mechanism, we construct a controlled clustered multi\-target benchmark\. This benchmark is designed to capture a multi\-resolution image summarization scenario in which visually similar images form semantic clusters and each cluster contains several near\-tie representative images\. Unless otherwise specified, we constructI=10I=10victim models, each containingn=50n=50items organized into55clusters with1010items per cluster\. The similarity matrix of each victim model is normalized to\[0,1\]\[0,1\]\. Inter\-cluster similarities are sampled from a low range, while intra\-cluster similarities are sampled from a moderate range\. Within each cluster, two representative candidates are assigned near\-tie similarity scores to the remaining items\. In the main benchmark, inter\-cluster similarities are sampled from\[0\.05,0\.12\]\[0\.05,0\.12\], ordinary intra\-cluster similarities from\[0\.44,0\.56\]\[0\.44,0\.56\], hub\-representative similarities from\[0\.76,0\.81\]\[0\.76,0\.81\], and runner\-up representative similarities from\[0\.75,0\.80\]\[0\.75,0\.80\]\.

All victim models share the same clustered representative structure, while small symmetric noise is added to the similarity matrices across models\. This shared\-but\-nonidentical construction is designed to reflect the multi\-target attack setting: the attacker must generate a single perturbation that degrades several related summarization models simultaneously\. Moreover, the near\-tie representative design prevents the attack from being dominated by a single obvious hub item, making the benchmark suitable for evaluating structure\-aware attacks under the multilinear\-extension objective\.

#### VI\-A3Feasible set and summary budgets

Following the multilinear\-extension formulation, each coordinatexν∈\[0,1\]x\_\{\\nu\}\\in\[0,1\]is interpreted as the probability or soft weight of selecting an item\. Thus, we use the cardinality\-budget relaxation

𝒳k=\{𝐱∈\[0,1\]n:∑ν=1nxν≤k\},\\mathcal\{X\}\_\{k\}=\\left\\\{\\mathbf\{x\}\\in\[0,1\]^\{n\}:\\sum\_\{\\nu=1\}^\{n\}x\_\{\\nu\}\\leq k\\right\\\},wherekkcontrols the expected summary size\. For the real\-data setting, we considerk∈\{5,10,15\}k\\in\\\{5,10,15\\\}, corresponding to summary ratios of10%10\\%,20%20\\%, and30%30\\%whenn=50n=50\. For the controlled clustered benchmark, we usek=5k=5, corresponding to selecting one representative item from each cluster on average\. After optimization, a deterministic summary is obtained by selecting the top\-kkcoordinates of𝐱\\mathbf\{x\}\.

#### VI\-A4Evaluation protocol and metrics

We evaluate each method from both continuous and discrete perspectives\. For the continuous evaluation, we report the multilinear\-extension utilityF​\(𝐱,Ω\)F\(\\mathbf\{x\},\\Omega\)\. For the discrete evaluation, we round the continuous solution by selecting the top\-kkentries of𝐱\\mathbf\{x\}and then evaluate the resulting summary under the discrete utilityf​\(Sk​\(𝐱\),Ω\)f\(S\_\{k\}\(\\mathbf\{x\}\),\\Omega\)\. All attacked and robust solutions are evaluated under the original clean similarity matrix, so that the reported degradation reflects the quality loss caused by the perturbation rather than a change in the evaluation objective itself\. For the controlled clustered benchmark, this protocol additionally allows us to interpret attack effectiveness in terms of whether the selected summary loses cluster coverage or fails to preserve representative items\.

For attack evaluation, we report three metrics:Avg\. Degradation,Success Ratio, andAttack Intensity\. Avg\. Degradation measures the average decrease in clean\-objective value caused by the attack\. Success Ratio measures the fraction of target models whose clean\-objective values are reduced by the generated perturbation\. Attack Intensity is the normalized average degradation\. For defense evaluation, we reportLoss,Robustness, andMitigation\. Loss measures the clean\-data utility gap between the robust solution and the greedy solution\. Robustness measures the stability of the robust solution when comparing clean and attacked settings\. Mitigation measures how much the defense reduces the attack effect relative to the attacked greedy solution\.

For the controlled clustered benchmark, we further evaluate the structural quality of the rounded summary using three indicators:Coverage,Hit, andRedundancy\. Coverage measures how many ground\-truth clusters are represented in the selected summary\. Hit measures whether the summary successfully selects the designated hub representatives\. Redundancy measures the extent to which the selected summary contains repeated information from only a few clusters\. Higher coverage and hit indicate better structural quality, whereas lower redundancy indicates a more diverse and representative summary\.

Finally, to connect summarization\-level degradation with downstream reliability, we evaluate downstream nearest\-neighbor classification on the controlled clustered benchmark\. Each cluster is treated as one class\. For each method, we round the continuous solution by selecting the top\-kkitems and use the selected summary as a small training set\. Each clean test sample is then assigned the label of its most similar selected summary item under the clean similarity matrix\. We report nearest\-neighbor classification accuracy \(NN Acc\.\) and downstreamRecovery\. NN Acc\. measures the usefulness of the selected summary for downstream classification, while Recovery measures the fraction of downstream accuracy loss recovered relative to the attacked summary\.

### VI\-BAttack Performance underlpl\_\{p\}\-Norm Constraints

We organize the attack evaluation into two complementary cases\. The first case considers the real\-data multilinear\-extension summarization model, which is directly aligned with our theoretical formulation and is used to examine whether structure\-aware similarity perturbations can produce measurable degradation beyond gradient\-based and random baselines\. The second case uses a controlled clustered multi\-target benchmark with explicit representative structure, which allows us to isolate the multi\-target attack mechanism and interpret degradation through cluster coverage, representative hits, and redundancy\. We report representative norm settings in the main text and defer additional norm\- and budget\-specific results to the Appendix\.

#### VI\-B1Real\-data multilinear\-extension summarization

We first evaluate the attack on the real\-data multilinear\-extension model\. This setting is directly aligned with the theoretical objective, but the multilinear extension also smooths the discrete utility over randomized subsets\. Therefore, the purpose of this case is not to show a large collapse of the real\-data summarization model, but to test whether a structure\-aware perturbation can produce measurable degradation beyond gradient\-based and random baselines\.

Choice of baselines\.The representative methods summarized in Table[I](https://arxiv.org/html/2606.11804#S2.T1)differ substantially in target setting and structural assumptions\. In particular, the methods in\[[1](https://arxiv.org/html/2606.11804#bib.bib45)\]do not explicitly address the continuous multi\-target setting considered here\. We therefore compare the proposed method with two directly applicable baselines: a representative gradient\-based baseline for general non\-convex min\-max optimization\[[25](https://arxiv.org/html/2606.11804#bib.bib44)\], and a random perturbation baseline sampled from the same norm\-constrained perturbation set\. The random baseline serves as a sanity check for whether utility degradation is caused by optimized structure\-aware perturbations rather than arbitrary bounded similarity noise\.

TABLE II:Attack comparison on the multilinear\-extension summarization model under representative norm constraints\. We useI=10I=10,n=50n=50,k=5k=5,λ=1\\lambda=1,Kattack=30K\_\{\\rm attack\}=30, andTattack=20T\_\{\\rm attack\}=20\. Random perturbation is averaged over 20 independent trials\.MethodAvg\. Deg\.↑\\uparrowSucc\. Ratio↑\\uparrowIntensity↑\\uparrowℓ1\\ell\_\{1\}\-norm constraint,ϵ=2\.0\\epsilon=2\.0Proposed attack0\.03290\.600\.000869PGD baseline0\.00970\.700\.000255Random perturbation\-0\.03550\.10\-0\.000938ℓ2\\ell\_\{2\}\-norm constraint,ϵ=2\.0\\epsilon=2\.0Proposed attack0\.05480\.700\.001448PGD baseline0\.00010\.700\.000002Random perturbation\-0\.03550\.40\-0\.000508

As shown in Table[II](https://arxiv.org/html/2606.11804#S6.T2), the proposed attack achieves the largest average degradation and attack intensity under both representativeℓ1\\ell\_\{1\}\- andℓ2\\ell\_\{2\}\-norm constraints\. Although PGD attains comparable or slightly higher success ratios in some cases, its degradation magnitude is much smaller\. The random perturbation baseline yields negative degradation in both representative settings, indicating that arbitrary feasible perturbations do not reliably reduce the clean summarization utility\. At the same time, the absolute degradation values are small, suggesting that the real\-data multilinear\-extension objective is relatively stable under bounded similarity\-level perturbations\.

![Refer to caption](https://arxiv.org/html/2606.11804v1/figs/realdata_l1_l2_avg_degradation_refined_labels_band.png)Figure 2:Real\-data budget sensitivity underℓ1\\ell\_\{1\}\- andℓ2\\ell\_\{2\}\-norm constraints\. Thexx\-axis reportslog10⁡ϵ\\log\_\{10\}\\epsilon, and theyy\-axis reports average degradation\. Shaded bands indicate the standard error across the 10 victim models\. Node labels show the mean average\-degradation values\. Random perturbation is averaged over 20 independent trials\.We further examine budget sensitivity in Fig\.[2](https://arxiv.org/html/2606.11804#S6.F2)\. The proposed attack algorithm becomes effective in moderate\-budget regimes, while random perturbations remain weak or negative in the most informative moderate\-budget region\. At very small budgets, all attacks may be weak, suggesting that the multilinear\-extension objective is relatively stable to small similarity perturbations\. This observation motivates the controlled benchmark below, where the representative structure is known and the attack mechanism can be more directly examined\. We also testedℓ∞\\ell\_\{\\infty\}\-bounded perturbations\. In the multilinear\-extension setting, the resulting degradation was weak and sometimes negative under the tested budgets, suggesting that the smoothed objective is relatively stable against small coordinate\-wise similarity perturbations\. We therefore report the detailedℓ∞\\ell\_\{\\infty\}results in the appendix\.

#### VI\-B2Controlled clustered multi\-target benchmark

We next evaluate the attacks on the controlled clustered benchmark\. This case is designed to isolate the multi\-target attack mechanism under a known representative structure\. Each victim model contains explicit clusters and near\-tie hub representatives, while the victim models share the same structural pattern with small model\-specific noise\. Therefore, this benchmark allows us to examine not only whether the objective value decreases, but also whether the selected summary loses cluster coverage, misses representative hubs, or becomes redundant\.

Utility degradation underℓ∞\\ell\_\{\\infty\}perturbations\.For the controlled clustered benchmark, the strongest and most stable effects are observed under theℓ∞\\ell\_\{\\infty\}\-norm constraint\. We additionally testℓ1\\ell\_\{1\}andℓ2\\ell\_\{2\}attacks on a near\-tie clustered variant, where the attack becomes effective after reducing the redundancy weight toλ=0\.1\\lambda=0\.1and increasingTattackT\_\{\\rm attack\}to 10\.

Table[III](https://arxiv.org/html/2606.11804#S6.T3)reports the attack performance underℓ∞\\ell\_\{\\infty\}\-bounded perturbations\. For low\-to\-moderate budgets, the proposed attack produces larger degradation than the PGD baseline\. Atϵ=0\.3\\epsilon=0\.3, the proposed attack improves the average degradation from5\.13245\.1324to6\.56956\.5695, and atϵ=0\.5\\epsilon=0\.5, the gap increases from2\.89142\.8914to6\.80446\.8044\. Both methods achieve a success ratio of1\.01\.0, so the advantage of the proposed attack comes from larger utility drops rather than more frequent successes\. When the budget increases toϵ=0\.7\\epsilon=0\.7, PGD becomes stronger, indicating that the advantage of the proposed attack is most pronounced when the perturbation budget is limited and the attack must exploit the shared representative structure\.

TABLE III:Attack comparison on the controlled clustered multilinear\-extension summarization benchmark\. We useI=10I=10,n=50n=50,k=5k=5,λ=0\.5\\lambda=0\.5,Kattack=30K\_\{\\rm attack\}=30, andTattack=5T\_\{\\rm attack\}=5\.ϵ\\boldsymbol\{\\epsilon\}MethodAvg\. Deg\.↑\\uparrowSucc\. Ratio↑\\uparrowIntensity↑\\uparrowℓ∞\\ell\_\{\\infty\}\-norm constraint0\.3Proposed attack6\.56951\.000\.1714PGD baseline5\.13241\.000\.13390\.5Proposed attack6\.80441\.000\.1776PGD baseline2\.89141\.000\.07550\.7Proposed attack10\.50721\.000\.2742PGD baseline14\.00131\.000\.3654

Additionalℓ1\\ell\_\{1\}andℓ2\\ell\_\{2\}results\.Table[IV](https://arxiv.org/html/2606.11804#S6.T4)reports the selected cluster\-data results underℓ1\\ell\_\{1\}andℓ2\\ell\_\{2\}constraints\. Compared with the original tight\-gap clustered setting used for theℓ∞\\ell\_\{\\infty\}study, this near\-tie clustered variant creates more competitive candidate summaries and therefore better exposes the effect of global\-budget perturbations\. Under theℓ1\\ell\_\{1\}\-norm constraint, the proposed attack achieves positive degradation and attack intensity, while random perturbation has nearly zero effect, indicating that arbitrary feasible perturbations are insufficient to explain the observed performance drop\. Under theℓ2\\ell\_\{2\}\-norm constraint, both optimized attacks substantially reduce the clean utility, with the proposed attack achieving the largest average degradation and intensity\. Although random perturbation also succeeds under this largerℓ2\\ell\_\{2\}budget, its intensity is much smaller than that of the optimized attacks, showing that the structure\-aware perturbation is considerably more damaging\.

TABLE IV:Attack comparison on the controlled clustered multilinear\-extension summarization benchmark\. We use the near\-tie clustered setting withI=10I=10,n=50n=50,k=5k=5,λ=0\.1\\lambda=0\.1,Kattack=30K\_\{\\rm attack\}=30, andTattack=10T\_\{\\rm attack\}=10\.Normϵ\\epsilonMethodAvg\. Deg\.↑\\uparrowSucc\.↑\\uparrowInt\.↑\\uparrowℓ1\\ell\_\{1\}2Proposed attack1\.60640\.400\.0390PGD baseline1\.60640\.400\.0390Random perturbation\-0\.00650\.00\-0\.0002ℓ2\\ell\_\{2\}5Proposed attack11\.12721\.000\.2705PGD baseline9\.15921\.000\.2226Random perturbation1\.41051\.000\.0343

Structural effects on rounded summaries\.Table[V](https://arxiv.org/html/2606.11804#S6.T5)further explains the utility degradation through the rounded summary structure\. Under both representative budgets, the proposed attack causes larger coverage loss, stronger reduction in representative\-hit ratio, and higher redundancy than the PGD baseline\. For example, whenϵ=0\.5\\epsilon=0\.5, Proposed attack reduces coverage from1\.0001\.000to0\.8200\.820and hit ratio from0\.5800\.580to0\.3200\.320, while increasing redundancy to0\.1800\.180\. These results show that the attack not only lowers continuous objective value, but also damages discrete summary by removing hub representatives and concentrating selections in fewer clusters\.

Overall, the two cases provide complementary evidence\. The real\-data multilinear\-extension setting shows measurable but budget\-sensitive vulnerability under optimized similarity perturbations\. The controlled clustered benchmark further reveals when this vulnerability becomes more pronounced: when multiple victim models share a near\-tie representative structure, a single bounded perturbation can systematically reduce utility and damage the rounded summary\. Thus, the proposed attack is best interpreted as a structure\-aware multi\-target attack that is most informative in low\-to\-moderate budget regimes, rather than as a uniformly strongest attack across all norms and budgets\.

TABLE V:Structural degradation of the selected summaries on the controlled clustered benchmark\. Coverage and representative hit ratio are higher for better summaries, while redundancy is lower\.ϵ\\boldsymbol\{\\epsilon\}MetricCleanProposed attackPGD attack0\.3Cov\.↑\\uparrow1\.0000\.8800\.980Δ\\DeltaCov\.↑\\uparrow0\.0000\.1200\.020Hit↑\\uparrow0\.5800\.4200\.500Δ\\DeltaHit↑\\uparrow0\.0000\.1600\.080Red\.↓\\downarrow0\.0000\.1200\.020Δ\\DeltaRed\.↑\\uparrow0\.0000\.1200\.0200\.5Cov\.↑\\uparrow1\.0000\.8200\.860Δ\\DeltaCov\.↑\\uparrow0\.0000\.1800\.140Hit↑\\uparrow0\.5800\.3200\.600Δ\\DeltaHit↑\\uparrow0\.0000\.260\-0\.020Red\.↓\\downarrow0\.0000\.1800\.140Δ\\DeltaRed\.↑\\uparrow0\.0000\.1800\.140

### VI\-CRobustness of the Defense Algorithm

We evaluate whether the proposed robust algorithm can reduce adversarial effects while preserving clean summarization quality\. The controlled clustered benchmark is used as the main defense testbed, since its known representative structure makes robustness and mitigation effects directly interpretable\. We also report MovieLens results as a real\-data sanity check for the multilinear\-extension summarization model\.

#### VI\-C1Controlled clustered benchmark

We compare the proposed robust method with a representative PGD\-based robust baseline under the same attack and evaluation protocol\. The goal is to examine whether robust optimization can reduce clean\-attacked variation, improve mitigation over the attacked greedy solution, and preserve clean\-data utility\.

TABLE VI:Defense comparison on the controlled clustered benchmark\. We use theℓ∞\\ell\_\{\\infty\}\-bounded setting withϵatt=0\.5\\epsilon\_\{\\rm att\}=0\.5,ϵdef=0\.02\\epsilon\_\{\\rm def\}=0\.02,γ=0\.1\\gamma=0\.1,L=10L=10,Krobust=30K\_\{\\rm robust\}=30, andTrobust=5T\_\{\\rm robust\}=5\.MethodLoss↓\\downarrowRobust\.↓\\downarrowMitig\.↑\\uparrowTime↓\\downarrowProposed robust\-0\.00920\.10290\.08262\.99PGD robust baseline\-0\.05260\.14640\.07574\.80

Table[VI](https://arxiv.org/html/2606.11804#S6.T6)shows that the proposed robust method provides a more favorable defense trade\-off on the controlled clustered benchmark\. It achieves lower clean\-attacked variation, slightly higher mitigation, and shorter runtime than the PGD robust baseline\. Both methods have slightly negative loss values, indicating that robust optimization does not incur observable clean\-utility sacrifice in this controlled setting\.

#### VI\-C2Real\-data sanity check

We also evaluate the defense methods on the MovieLens real\-data multilinear\-extension model\. Since this setting does not provide an explicit representative structure, the defense effect is weaker and more sensitive to the perturbation geometry; we therefore treat it as a sanity check rather than the main defense evidence\.

TABLE VII:Real\-data defense comparison on MovieLens under representative norm constraints\.Normϵatt\\epsilon\_\{\\rm att\}ϵdef\\epsilon\_\{\\rm def\}MethodLoss↓\\downarrowRobust\.↓\\downarrowMitig\.↑\\uparrowTime↓\\downarrowℓ1\\ell\_\{1\}22Proposed robust0\.00050\.0041\-0\.00112\.27PGD robust baseline0\.01840\.0012\-0\.01803\.03ℓ2\\ell\_\{2\}22Proposed robust0\.00050\.00440\.00091\.24PGD robust baseline0\.02340\.0012\-0\.02222\.00ℓ∞\\ell\_\{\\infty\}0\.10\.1Proposed robust0\.02050\.0105\-0\.02231\.28PGD robust baseline0\.02550\.0007\-0\.02831\.86

Table[VII](https://arxiv.org/html/2606.11804#S6.T7)shows that the proposed robust method generally incurs smaller clean\-data loss than the PGD robust baseline on MovieLens\. However, the mitigation values are close to zero and depend on the norm constraint, confirming that real\-data robust protection is more parameter\-sensitive than in the controlled clustered benchmark\. These results support the use of the controlled benchmark as the main defense evaluation while providing additional evidence that the proposed method can preserve clean utility in the real\-data multilinear\-extension setting\.

#### VI\-C3Defense Sensitivity under Different Norm Constraints

Table[VIII](https://arxiv.org/html/2606.11804#S6.T8)reports an additional defense sensitivity study under different norm constraints on the controlled clustered benchmark and the MovieLens real\-data setting\. This experiment is intended as a cross\-norm sanity check rather than the main defense comparison, since the effectiveness of robust optimization depends on the geometry of the perturbation set, the attack budget, and the underlying similarity structure\.

On the controlled clustered benchmark, the proposed robust method performs favorably under theℓ1\\ell\_\{1\}\-norm constraint: it incurs almost no clean\-data loss and avoids the large negative mitigation observed for the PGD robust baseline\. Under theℓ2\\ell\_\{2\}\-norm constraint, however, both methods obtain negative mitigation, indicating that this setting is difficult for the tested defense algorithms and that robust optimization does not effectively improve over the attacked greedy solution\. Under theℓ∞\\ell\_\{\\infty\}\-norm constraint, both methods achieve positive mitigation; the proposed method has smaller clean\-data loss and slightly lower robustness variation, whereas the PGD robust baseline attains larger mitigation\. These results suggest that defense performance on the clustered benchmark is sensitive to the norm geometry and should be interpreted as a robustness–mitigation trade\-off rather than a uniform dominance result\.

On the MovieLens real\-data setting, the robustness values are small for both methods across all tested norms, suggesting that the real\-data objective is relatively stable under the considered bounded perturbations\. The proposed robust method generally incurs smaller clean\-data loss than the PGD robust baseline, but the mitigation values remain close to zero and can be negative\. This indicates that, in the real\-data setting, robust protection is more parameter\-sensitive and the benefit of defense is weaker than in the structured clustered benchmark\. Overall, Table[VIII](https://arxiv.org/html/2606.11804#S6.T8)shows that the proposed defense can provide favorable trade\-offs in representative settings, but its effectiveness is not uniform across all norm constraints\. These results support our main\-text focus on the controlledℓ∞\\ell\_\{\\infty\}\-bounded clustered benchmark, where the attack induces clear structural degradation and the defense effect is more interpretable\.

TABLE VIII:Defense sensitivity under different norm constraints on the controlled clustered benchmark and MovieLens\.Normϵ\\boldsymbol\{\\epsilon\}MethodLoss↓\\downarrowRobust\.↓\\downarrowMitig\.↑\\uparrowControlled clustered benchmarkℓ1\\ell\_\{1\}2Proposed robust\-0\.00250\.04720\.0000PGD robust0\.17230\.0375\-0\.1910ℓ2\\ell\_\{2\}2Proposed robust0\.23520\.1960\-0\.4377PGD robust0\.19490\.2251\-0\.4286ℓ∞\\ell\_\{\\infty\}0\.5Proposed robust0\.01630\.14450\.0187PGD robust\-0\.05260\.15490\.0668MovieLens real\-data settingℓ1\\ell\_\{1\}2Proposed robust0\.00050\.0041\-0\.0011PGD robust0\.01840\.0012\-0\.0180ℓ2\\ell\_\{2\}2Proposed robust0\.00050\.00440\.0009PGD robust0\.02340\.0012\-0\.0222ℓ∞\\ell\_\{\\infty\}0\.1Proposed robust0\.02050\.0105\-0\.0223PGD robust0\.02550\.0007\-0\.0283

### VI\-DDownstream Evaluation on the Controlled Benchmark

The previous metrics evaluate summarization utility and structural quality\. We now examine whether such degradation also affects downstream task reliability on the controlled clustered benchmark\. Following the downstream protocol described in the experimental setup, we use the rounded top\-kksummaries as small training sets and evaluate nearest\-neighbor classification on clean test samples\. An auxiliary real\-data downstream evaluation on MovieLens is provided in the Appendix, where the downstream labels are less directly aligned with the summarization objective\.

TABLE IX:Downstream classification performance on the controlled clustered benchmark\.MethodCoverage↑\\uparrowNN Acc\.↑\\uparrowRecovery↑\\uparrowClean summary1\.0001\.0001\.000Proposed attack0\.8200\.8200\.000PGD attack0\.8600\.8600\.222Proposed robust1\.0001\.0001\.000PGD robust baseline1\.0001\.0001\.000

Table[IX](https://arxiv.org/html/2606.11804#S6.T9)shows that structural degradation can translate into downstream performance loss\. The proposed attack reduces cluster coverage from1\.0001\.000to0\.8200\.820, and NN Acc\. drops accordingly from1\.0001\.000to0\.8200\.820\. The PGD attack also reduces downstream accuracy, but the drop is smaller\. After robust optimization, both robust methods recover full cluster coverage and restore NN Acc\. to1\.0001\.000\. These results indicate that preserving class/cluster coverage is critical for the task\-level reliability of the selected summary\.

![Refer to caption](https://arxiv.org/html/2606.11804v1/figs/cluster_downstream_accuracy_attack_defense_refined.png)Figure 3:Downstream NN accuracy under attack and defense on the controlled clustered benchmark\.Fig\.[3](https://arxiv.org/html/2606.11804#S6.F3)visually summarizes the downstream effect: attacks reduce NN accuracy, whereas robust summaries recover full task\-level accuracy by restoring cluster coverage\.

## VIIConclusion

This paper investigated multi\-target robustness evaluation for continuous data summarization under similarity\-level adversarial perturbations\. We established a DR\-submodular formulation for a class of similarity\-based summarization objectives via multilinear extension andmm\-weak monotonicity, and used this structure to develop approximation algorithms for multi\-target attack generation and robust defense\. Empirical results on real\-data multilinear\-extension summarization and a controlled clustered benchmark show measurable, budget\-sensitive vulnerabilities under optimized similarity perturbations\. The controlled benchmark further reveals that attacks can degrade rounded summary structure and reduce downstream task performance, while robust summaries can recover task\-level reliability by restoring class/cluster coverage\. These findings highlight data summarization as a security\-relevant upstream component in trustworthy AI pipelines\. They also show that robust protection remains sensitive to data structure, perturbation geometry, and parameter choices, leaving practical robust summarization as an important direction for future work\.

### \-AProofs for Sec\.[III](https://arxiv.org/html/2606.11804#S3)

#### \-A1Several properties in Sec\.[III](https://arxiv.org/html/2606.11804#S3)

For a set functionf:2Ω→ℝf:2^\{\\Omega\}\\to\\mathbb\{R\}, its multilinear extensionF:\[0,1\]n→ℝF:\[0,1\]^\{n\}\\to\\mathbb\{R\}is defined as

F​\(𝐱\)=𝔼S∼𝐱​\[f​\(S\)\]=∑S⊆Ωf​\(S\)​∏i∈Sxi​∏i∉S\(1−xi\),F\(\\mathbf\{x\}\)=\\mathbb\{E\}\_\{S\\sim\\mathbf\{x\}\}\[f\(S\)\]=\\sum\_\{S\\subseteq\\Omega\}f\(S\)\\prod\_\{i\\in S\}x\_\{i\}\\prod\_\{i\\notin S\}\(1\-x\_\{i\}\),where each elementi∈Ωi\\in\\Omegais independently included inSSwith probabilityxix\_\{i\}\. SinceFFis a multilinear polynomial, it is continuously differentiable and twice differentiable on\[0,1\]n\[0,1\]^\{n\}\. Moreover, ifffis submodular, then its multilinear extensionFFis DR\-submodular\. Indeed, for any distincti,ji,j,

∂2F​\(𝐱\)∂xi​∂xj\\displaystyle\\frac\{\\partial^\{2\}F\(\\mathbf\{x\}\)\}\{\\partial x\_\{i\}\\partial x\_\{j\}\}=\\displaystyle=𝔼S∼𝐱−\{i,j\}\[f\(S∪\{i,j\}\)−f\(S∪\{i\}\)\\displaystyle\\mathbb\{E\}\_\{S\\sim\\mathbf\{x\}\_\{\-\\\{i,j\\\}\}\}\\left\[f\(S\\cup\\\{i,j\\\}\)\-f\(S\\cup\\\{i\\\}\)\\right\.−f\(S∪\{j\}\)\+f\(S\)\]\\displaystyle\-\\left\.f\(S\\cup\\\{j\\\}\)\+f\(S\)\\right\]≤\\displaystyle\\leq0\.\\displaystyle 0\.In addition, ifffis non\-negative, thenFFis non\-negative\. Ifffismm\-weakly monotone, namely

f​\(A∪B\)≥m​f​\(A\),∀A,B⊆Ω,f\(A\\cup B\)\\geq mf\(A\),\\qquad\\forall A,B\\subseteq\\Omega,then its multilinear extension is alsomm\-weakly monotone:

F​\(𝐱∨𝐲\)≥m​F​\(𝐱\),∀𝐱,𝐲∈\[0,1\]n\.F\(\\mathbf\{x\}\\vee\\mathbf\{y\}\)\\geq mF\(\\mathbf\{x\}\),\\qquad\\forall\\mathbf\{x\},\\mathbf\{y\}\\in\[0,1\]^\{n\}\.Supposeffis DR\-submodular on𝒟\\mathcal\{D\}\. Then the following statements hold\[[3](https://arxiv.org/html/2606.11804#bib.bib49)\]\.

1. 1\.Gradient monotonicity\.Ifffis differentiable, then ∇f​\(𝐱\)≤∇f​\(𝐲\),∀𝐱≥𝐲\.\\nabla f\(\\mathbf\{x\}\)\\leq\\nabla f\(\\mathbf\{y\}\),\\qquad\\forall\\mathbf\{x\}\\geq\\mathbf\{y\}\.
2. 2\.Hessian negativity\.Ifffis twice differentiable, then ∂2f​\(𝐱\)∂𝐱i​∂𝐱j≤0,∀𝐱∈𝒟,∀i,j\.\\frac\{\\partial^\{2\}f\(\\mathbf\{x\}\)\}\{\\partial\\mathbf\{x\}\_\{i\}\\partial\\mathbf\{x\}\_\{j\}\}\\leq 0,\\qquad\\forall\\mathbf\{x\}\\in\\mathcal\{D\},\\ \\forall i,j\.
3. 3\.First\-order condition\.Ifffis continuously differentiable, then ⟨∇f​\(𝐱\),𝐲−𝐱⟩≥f​\(𝐱∨𝐲\)\+f​\(𝐱∧𝐲\)−2​f​\(𝐱\),∀𝐱,𝐲∈𝒟\.\\langle\\nabla f\(\\mathbf\{x\}\),\\mathbf\{y\}\-\\mathbf\{x\}\\rangle\\geq f\(\\mathbf\{x\}\\vee\\mathbf\{y\}\)\+f\(\\mathbf\{x\}\\wedge\\mathbf\{y\}\)\-2f\(\\mathbf\{x\}\),\\qquad\\forall\\mathbf\{x\},\\mathbf\{y\}\\in\\mathcal\{D\}\.\(10\)

In order to prove the smoothness of the model, we provide the definition as follows firstly\.

###### Definition 3\(\[[23](https://arxiv.org/html/2606.11804#bib.bib9),[28](https://arxiv.org/html/2606.11804#bib.bib10)\]\)\.

A functionf​\(𝐱,𝐲\)f\(\\mathbf\{x\},\\mathbf\{y\}\)is said to beLL\-smoothness if there exists a constantL=max⁡\{L𝐱,L𝐲\}L=\\max\\\{L\_\{\\mathbf\{x\}\},L\_\{\\mathbf\{y\}\}\\\}such that

∥∇𝐱f​\(𝐱1,𝐲1\)−∇𝐱f​\(𝐱2,𝐲2\)∥≤L𝐱​\(∥𝐱1−𝐱2∥\+∥𝐲1−𝐲2∥\),\\displaystyle\\lVert\\nabla\_\{\\mathbf\{x\}\}f\(\\mathbf\{x\}\_\{1\},\\mathbf\{y\}\_\{1\}\)\-\\nabla\_\{\\mathbf\{x\}\}f\(\\mathbf\{x\}\_\{2\},\\mathbf\{y\}\_\{2\}\)\\rVert\\leq L\_\{\\mathbf\{x\}\}\(\\lVert\\mathbf\{x\}\_\{1\}\-\\mathbf\{x\}\_\{2\}\\rVert\+\\lVert\\mathbf\{y\}\_\{1\}\-\\mathbf\{y\}\_\{2\}\\rVert\),∥∇𝐲f​\(𝐱1,𝐲1\)−∇𝐲f​\(𝐱2,𝐲2\)∥≤L𝐲​\(∥𝐱1−𝐱2∥\+∥𝐲1−𝐲2∥\)\.\\displaystyle\\lVert\\nabla\_\{\\mathbf\{y\}\}f\(\\mathbf\{x\}\_\{1\},\\mathbf\{y\}\_\{1\}\)\-\\nabla\_\{\\mathbf\{y\}\}f\(\\mathbf\{x\}\_\{2\},\\mathbf\{y\}\_\{2\}\)\\rVert\\leq L\_\{\\mathbf\{y\}\}\(\\lVert\\mathbf\{x\}\_\{1\}\-\\mathbf\{x\}\_\{2\}\\rVert\+\\lVert\\mathbf\{y\}\_\{1\}\-\\mathbf\{y\}\_\{2\}\\rVert\)\.where∥⋅∥\\lVert\\cdot\\rVertdenotes the Euclidean norm \(l2l\_\{2\}\-norm\)\.

###### Lemma 4\.

LetFFbe the multilinear extension of a bounded set functionf:2Ω→ℝf:2^\{\\Omega\}\\to\\mathbb\{R\}\. ThenFFis continuously differentiable andLL\-smooth on\[0,1\]n\[0,1\]^\{n\}with

L=sup𝐱∈\[0,1\]n‖∇2F​\(𝐱\)‖2<∞\.L=\\sup\_\{\\mathbf\{x\}\\in\[0,1\]^\{n\}\}\\\|\\nabla^\{2\}F\(\\mathbf\{x\}\)\\\|\_\{2\}<\\infty\.

In particular, the first\-order condition implies that if𝐲≥𝐱\\mathbf\{y\}\\geq\\mathbf\{x\}, then

⟨∇f​\(𝐱\),𝐲−𝐱⟩≥f​\(𝐲\)−f​\(𝐱\),\\langle\\nabla f\(\\mathbf\{x\}\),\\mathbf\{y\}\-\\mathbf\{x\}\\rangle\\geq f\(\\mathbf\{y\}\)\-f\(\\mathbf\{x\}\),which shows that DR\-submodular functions are up\-concave, i\.e\., concave along any non\-negative or non\-positive direction\[[13](https://arxiv.org/html/2606.11804#bib.bib7)\]\. We evaluate constrained DR\-submodular maximization algorithms using the standard notion of approximation\.

#### \-A2Proof of Lem\.[1](https://arxiv.org/html/2606.11804#Thmlemma1)

###### Proof\.

We first prove the properties of the discrete utility

f​\(S,Ω\)=r​\(S,Ω\)−λn​q​\(S,Ω\),f\(S,\\Omega\)=r\(S,\\Omega\)\-\\frac\{\\lambda\}\{n\}q\(S,\\Omega\),where

r​\(S,Ω\)=∑μ∈Ωmaxν∈S⁡sμ,ν,q​\(S,Ω\)=∑μ∈S∑ν∈S,ν≠μsμ,ν\.r\(S,\\Omega\)=\\sum\_\{\\mu\\in\\Omega\}\\max\_\{\\nu\\in S\}s\_\{\\mu,\\nu\},\\quad q\(S,\\Omega\)=\\sum\_\{\\mu\\in S\}\\sum\_\{\\nu\\in S,\\nu\\neq\\mu\}s\_\{\\mu,\\nu\}\.
First, by the definition ofρΩ\\rho\_\{\\Omega\}, for any nonemptyS⊆ΩS\\subseteq\\Omega,

λn​q​\(S,Ω\)≤ρΩ​r​\(S,Ω\)\.\\frac\{\\lambda\}\{n\}q\(S,\\Omega\)\\leq\\rho\_\{\\Omega\}r\(S,\\Omega\)\.Since0≤ρΩ<10\\leq\\rho\_\{\\Omega\}<1, we have

f​\(S,Ω\)≥\(1−ρΩ\)​r​\(S,Ω\)≥0\.f\(S,\\Omega\)\\geq\(1\-\\rho\_\{\\Omega\}\)r\(S,\\Omega\)\\geq 0\.Also,f​\(∅,Ω\)=0f\(\\emptyset,\\Omega\)=0by convention\. Henceffis non\-negative\.

Second, the facility\-location termr​\(S,Ω\)r\(S,\\Omega\)is submodular\. Indeed, for anyA⊆B⊆ΩA\\subseteq B\\subseteq\\Omegaande∉Be\\notin B,

r​\(A∪\{e\},Ω\)−r​\(A,Ω\)=∑μ∈Ω\[sμ,e−maxν∈A⁡sμ,ν\]\+,r\(A\\cup\\\{e\\\},\\Omega\)\-r\(A,\\Omega\)=\\sum\_\{\\mu\\in\\Omega\}\\left\[s\_\{\\mu,e\}\-\\max\_\{\\nu\\in A\}s\_\{\\mu,\\nu\}\\right\]\_\{\+\},which is no smaller than

∑μ∈Ω\[sμ,e−maxν∈B⁡sμ,ν\]\+=r​\(B∪\{e\},Ω\)−r​\(B,Ω\),\\sum\_\{\\mu\\in\\Omega\}\\left\[s\_\{\\mu,e\}\-\\max\_\{\\nu\\in B\}s\_\{\\mu,\\nu\}\\right\]\_\{\+\}=r\(B\\cup\\\{e\\\},\\Omega\)\-r\(B,\\Omega\),becauseA⊆BA\\subseteq B\. Thusrris submodular\.

On the other hand, the redundancy termq​\(S,Ω\)q\(S,\\Omega\)is supermodular\. For anyA⊆B⊆ΩA\\subseteq B\\subseteq\\Omegaande∉Be\\notin B,

q​\(A∪\{e\},Ω\)−q​\(A,Ω\)\\displaystyle q\(A\\cup\\\{e\\\},\\Omega\)\-q\(A,\\Omega\)=\\displaystyle=∑ν∈A\(se,ν\+sν,e\)\\displaystyle\\sum\_\{\\nu\\in A\}\(s\_\{e,\\nu\}\+s\_\{\\nu,e\}\)≤\\displaystyle\\leq∑ν∈B\(se,ν\+sν,e\)=q​\(B∪\{e\},Ω\)−q​\(B,Ω\),\\displaystyle\\sum\_\{\\nu\\in B\}\(s\_\{e,\\nu\}\+s\_\{\\nu,e\}\)=q\(B\\cup\\\{e\\\},\\Omega\)\-q\(B,\\Omega\),where the inequality follows fromsμ,ν≥0s\_\{\\mu,\\nu\}\\geq 0\. Therefore,−λn​q\-\\frac\{\\lambda\}\{n\}qis submodular, and henceffis submodular\.

Third, we prove weak monotonicity\. For anyA,B⊆ΩA,B\\subseteq\\Omega, letC=A∪BC=A\\cup B\. Sincerris monotone,r​\(C,Ω\)≥r​\(A,Ω\)r\(C,\\Omega\)\\geq r\(A,\\Omega\)\. Using the definition ofρΩ\\rho\_\{\\Omega\}, we obtain

f​\(C,Ω\)≥\(1−ρΩ\)​r​\(C,Ω\)≥\(1−ρΩ\)​r​\(A,Ω\)\.f\(C,\\Omega\)\\geq\(1\-\\rho\_\{\\Omega\}\)r\(C,\\Omega\)\\geq\(1\-\\rho\_\{\\Omega\}\)r\(A,\\Omega\)\.Moreover,f​\(A,Ω\)≤r​\(A,Ω\)f\(A,\\Omega\)\\leq r\(A,\\Omega\)\. Therefore,

f​\(A∪B,Ω\)≥\(1−ρΩ\)​f​\(A,Ω\)\.f\(A\\cup B,\\Omega\)\\geq\(1\-\\rho\_\{\\Omega\}\)f\(A,\\Omega\)\.Thus,ffismΩm\_\{\\Omega\}\-weakly monotone withmΩ=1−ρΩm\_\{\\Omega\}=1\-\\rho\_\{\\Omega\}\.

Finally, sinceF​\(𝐱,Ω\)F\(\\mathbf\{x\},\\Omega\)is the multilinear extension off​\(S,Ω\)f\(S,\\Omega\), the standard properties of multilinear extensions imply that non\-negativity, submodularity, andmΩm\_\{\\Omega\}\-weak monotonicity offfrespectively lead to non\-negativity, DR\-submodularity, andmΩm\_\{\\Omega\}\-weak monotonicity ofFF\. This completes the proof\. ∎

### \-BProofs for Sec\.[IV\-A](https://arxiv.org/html/2606.11804#S4.SS1)

#### \-B1Proof of Lemmas

Proof of Lem\.[3](https://arxiv.org/html/2606.11804#Thmlemma3)

###### Proof\.

According to the iteration rule of Alg\.[2](https://arxiv.org/html/2606.11804#alg2), i\.e\.,

𝐯k\+1=argmin𝐯∈𝒫∥𝐯−\(𝐯k−η∇𝐯ϕ\(𝐯k,𝐰k,\{𝐱Ti\(𝐯k,𝐰k\)\}\)\)∥2,\\mathbf\{v\}\_\{k\+1\}=\\arg\\min\_\{\\mathbf\{v\}\\in\\mathcal\{P\}\}\\lVert\\mathbf\{v\}\-\(\\mathbf\{v\}\_\{k\}\-\\eta\\nabla\_\{\\mathbf\{v\}\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\},\\\{\\mathbf\{x\}^\{i\}\_\{T\}\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\}\)\\\}\)\)\\rVert^\{2\},we obtain the following inequality for any𝐯∈𝒫\\mathbf\{v\}\\in\\mathcal\{P\}:

∥𝐯k\+1−𝐯∥22\\displaystyle\\lVert\\mathbf\{v\}\_\{k\+1\}\-\\mathbf\{v\}\\rVert\_\{2\}^\{2\}≤\\displaystyle\\leq∥𝐯k−η​∇𝐯ϕ​\(𝐯k,𝐰k,\{𝐱Ti​\(𝐯k,𝐰k\)\}\)−𝐯∥2\\displaystyle\\lVert\\mathbf\{v\}\_\{k\}\-\\eta\\nabla\_\{\\mathbf\{v\}\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\},\\\{\\mathbf\{x\}\_\{T\}^\{i\}\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\}\)\\\}\)\-\\mathbf\{v\}\\rVert^\{2\}=\\displaystyle=∥𝐯k−𝐯∥2−2​η​⟨∇𝐯ϕ​\(𝐯k,𝐰k,\{𝐱Ti​\(𝐯k,𝐰k\)\}\),𝐯k−𝐯⟩⏟:=𝐀\\displaystyle\\lVert\\mathbf\{v\}\_\{k\}\-\\mathbf\{v\}\\rVert^\{2\}\-2\\eta\\underbrace\{\\langle\\nabla\_\{\\mathbf\{v\}\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\},\\\{\\mathbf\{x\}\_\{T\}^\{i\}\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\}\)\\\}\),\\mathbf\{v\}\_\{k\}\-\\mathbf\{v\}\\rangle\}\_\{:=\{\\bf A\}\}\+η2​∥∇𝐯ϕ​\(𝐯k,𝐰k,\{𝐱Ti​\(𝐯k,𝐰k\)\}\)∥2,\\displaystyle\+\\eta^\{2\}\\lVert\\nabla\_\{\\mathbf\{v\}\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\},\\\{\\mathbf\{x\}\_\{T\}^\{i\}\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\}\)\\\}\)\\rVert^\{2\},which can be expressed as

𝐀≥\\displaystyle\{\\bf A\}\\geq∥𝐯k\+1−𝐯∥22−∥𝐯k−𝐯∥22​η\\displaystyle\\frac\{\\lVert\\mathbf\{v\}\_\{k\+1\}\-\\mathbf\{v\}\\rVert\_\{2\}^\{2\}\-\\lVert\\mathbf\{v\}\_\{k\}\-\\mathbf\{v\}\\rVert^\{2\}\}\{2\\eta\}−−η​∥∇𝐯ϕ​\(𝐯k,𝐰k,\{𝐱Ti​\(𝐯k,𝐰k\)\}\)∥22\.\\displaystyle\-\\frac\{\-\\eta\\lVert\\nabla\_\{\\mathbf\{v\}\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\},\\\{\\mathbf\{x\}\_\{T\}^\{i\}\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\}\)\\\}\)\\rVert^\{2\}\}\{2\}\.Combining with the convexity of the functionϕ​\(𝐯,𝐰,\{𝐱i\}\)\\phi\(\\mathbf\{v\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)w\.r\.t\.𝐯\\mathbf\{v\}, we have

ϕ​\(𝐯,𝐰k,\{𝐱Ti​\(𝐯k,𝐰k\)\}\)−ϕ​\(𝐯k,𝐰k,\{𝐱Ti​\(𝐯k,𝐰k\)\}\)\\displaystyle\\phi\(\\mathbf\{v\},\\mathbf\{w\}\_\{k\},\\\{\\mathbf\{x\}\_\{T\}^\{i\}\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\}\)\\\}\)\-\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\},\\\{\\mathbf\{x\}\_\{T\}^\{i\}\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\}\)\\\}\)≥\\displaystyle\\geq⟨∇𝐯ϕ​\(𝐯k,𝐰k,\{𝐱Ti​\(𝐯k,𝐰k\)\}\),𝐯−𝐯k⟩⏟𝐀\\displaystyle\\underbrace\{\\left\\langle\\nabla\_\{\\mathbf\{v\}\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\},\\\{\\mathbf\{x\}\_\{T\}^\{i\}\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\}\)\\\}\),\\mathbf\{v\}\-\\mathbf\{v\}\_\{k\}\\right\\rangle\}\_\{\{\\bf A\}\}≥\\displaystyle\\geq∥𝐯k\+1−𝐯∥2−∥𝐯k−𝐯∥22​η\\displaystyle\\frac\{\\lVert\\mathbf\{v\}\_\{k\+1\}\-\\mathbf\{v\}\\rVert^\{2\}\-\\lVert\\mathbf\{v\}\_\{k\}\-\\mathbf\{v\}\\rVert^\{2\}\}\{2\\eta\}−η2​∥∇𝐯ϕ​\(𝐯k,𝐰k,\{𝐱Ti​\(𝐯k,𝐰k\)\}\)∥2\\displaystyle\-\\frac\{\\eta\}\{2\}\\lVert\\nabla\_\{\\mathbf\{v\}\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\},\\\{\\mathbf\{x\}\_\{T\}^\{i\}\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\}\)\\\}\)\\rVert^\{2\}≥\\displaystyle\\geq∥𝐯k\+1−𝐯∥2−∥𝐯k−𝐯∥22​η−η​M22\.\\displaystyle\\frac\{\\lVert\\mathbf\{v\}\_\{k\+1\}\-\\mathbf\{v\}\\rVert^\{2\}\-\\lVert\\mathbf\{v\}\_\{k\}\-\\mathbf\{v\}\\rVert^\{2\}\}\{2\\eta\}\-\\frac\{\\eta M^\{2\}\}\{2\}\.where the last inequality follows from the boundedness of∇𝐯ϕ\\nabla\_\{\\mathbf\{v\}\}\\phias descried in Eq\. \([6](https://arxiv.org/html/2606.11804#S4.E6)\)\. ∎

#### \-B2Proof of Theorems

Proof of Thm\.[1](https://arxiv.org/html/2606.11804#Thmtheorem1)

###### Proof\.

Firstly, we show that the output𝐱T\\mathbf\{x\}\_\{T\}is feasible\. Due to𝐝t≤𝐝¯t\\mathbf\{d\}\_\{t\}\\leq\\bar\{\\mathbf\{d\}\}\_\{t\}and the set𝒳\\mathcal\{X\}is down\-closed convex, we have𝐝t∈𝒳\\mathbf\{d\}\_\{t\}\\in\\mathcal\{X\}\. Combined that𝐱T\\mathbf\{x\}\_\{T\}is the combination of all iterations𝐝t,t=1,…​T−1\\mathbf\{d\}\_\{t\},t=1,\\ldots T\-1\. According to the smoothness of functionF​\(𝐯,𝐱\)F\(\\mathbf\{v\},\\mathbf\{x\}\)and Eq\. \([5](https://arxiv.org/html/2606.11804#S4.E5)\), we have the following inequality for all𝐱∈𝒳\\mathbf\{x\}\\in\\mathcal\{X\}

F​\(𝐯,𝐱t\+1\)−F​\(𝐯,𝐱t\)\\displaystyle F\(\\mathbf\{v\},\\mathbf\{x\}\_\{t\+1\}\)\-F\(\\mathbf\{v\},\\mathbf\{x\}\_\{t\}\)≥\\displaystyle\\geq⟨∇F​\(𝐯,𝐱t\),𝐱t\+1−𝐱t⟩−L2​∥𝐱t\+1−𝐱t∥2\\displaystyle\\langle\\nabla F\(\\mathbf\{v\},\\mathbf\{x\}\_\{t\}\),\\mathbf\{x\}\_\{t\+1\}\-\\mathbf\{x\}\_\{t\}\\rangle\-\\frac\{L\}\{2\}\\lVert\\mathbf\{x\}\_\{t\+1\}\-\\mathbf\{x\}\_\{t\}\\rVert^\{2\}≥\([5](https://arxiv.org/html/2606.11804#S4.E5)\)\\displaystyle\\overset\{\\eqref\{eq:pre\_equ\}\}\{\\geq\}⟨g​\(𝐱t\),1T​𝐝t⟩−L2​T2​∥𝐝t∥2\\displaystyle\\langle g\(\\mathbf\{x\}\_\{t\}\),\\frac\{1\}\{T\}\\mathbf\{d\}\_\{t\}\\rangle\-\\frac\{L\}\{2T^\{2\}\}\\lVert\\mathbf\{d\}\_\{t\}\\rVert^\{2\}≥\(a\)\\displaystyle\\overset\{\(a\)\}\{\\geq\}1T​⟨g​\(𝐱t\),𝐱⟩−L2​T2​D2\\displaystyle\\frac\{1\}\{T\}\\langle g\(\\mathbf\{x\}\_\{t\}\),\\mathbf\{x\}\\rangle\-\\frac\{L\}\{2T^\{2\}\}D^\{2\}≥\(b\)\\displaystyle\\overset\{\(b\)\}\{\\geq\}1T​⟨g​\(𝐱t\),𝐱∨𝐱t−𝐱t⟩−L2​T2​D2\\displaystyle\\frac\{1\}\{T\}\\langle g\(\\mathbf\{x\}\_\{t\}\),\\mathbf\{x\}\\vee\\mathbf\{x\}\_\{t\}\-\\mathbf\{x\}\_\{t\}\\rangle\-\\frac\{L\}\{2T^\{2\}\}D^\{2\}≥\(c\)\\displaystyle\\overset\{\(c\)\}\{\\geq\}1T​⟨∇F​\(𝐯,𝐱t\),𝐱∨𝐱t−𝐱t⟩−L2​T2​D2\\displaystyle\\frac\{1\}\{T\}\\langle\\nabla F\(\\mathbf\{v\},\\mathbf\{x\}\_\{t\}\),\\mathbf\{x\}\\vee\\mathbf\{x\}\_\{t\}\-\\mathbf\{x\}\_\{t\}\\rangle\-\\frac\{L\}\{2T^\{2\}\}D^\{2\}≥\(d\)\\displaystyle\\overset\{\(d\)\}\{\\geq\}1T​\[F​\(𝐯,𝐱∨𝐱t\)−F​\(𝐯,𝐱t\)\]−L2​T2​D2\\displaystyle\\frac\{1\}\{T\}\\left\[F\(\\mathbf\{v\},\\mathbf\{x\}\\vee\\mathbf\{x\}\_\{t\}\)\-F\(\\mathbf\{v\},\\mathbf\{x\}\_\{t\}\)\\right\]\-\\frac\{L\}\{2T^\{2\}\}D^\{2\}≥\(f\)\\displaystyle\\overset\{\(f\)\}\{\\geq\}1T​\[m​F​\(𝐯,𝐱\)−F​\(𝐯,𝐱t\)\]−L2​T2​D2\\displaystyle\\frac\{1\}\{T\}\\left\[mF\(\\mathbf\{v\},\\mathbf\{x\}\)\-F\(\\mathbf\{v\},\\mathbf\{x\}\_\{t\}\)\\right\]\-\\frac\{L\}\{2T^\{2\}\}D^\{2\}where\(a\)\(a\)is according to the Step 4 in Alg\.[1](https://arxiv.org/html/2606.11804#alg1),\(b\)\(b\)follows from the fact that𝐱\+𝐱t≥𝐱∨𝐱t\\mathbf\{x\}\+\\mathbf\{x\}\_\{t\}\\geq\\mathbf\{x\}\\vee\\mathbf\{x\}\_\{t\}for all𝐱,𝐱t∈𝒳\\mathbf\{x\},\\mathbf\{x\}\_\{t\}\\in\\mathcal\{X\}, and\(c\)\(c\)is a consequence of the definitiong​\(𝐱t\)=∇F​\(𝐯,𝐱t\)∨𝟎g\(\\mathbf\{x\}\_\{t\}\)=\\nabla F\(\\mathbf\{v\},\\mathbf\{x\}\_\{t\}\)\\vee\\mathbf\{0\},\(d\)\(d\)and\(f\)\(f\)are obtained from DR\-submodularity and monotonicity, respectively\. Thus, we have

F​\(𝐯,𝐱t\+1\)−m​F​\(𝐯,𝐱\)\\displaystyle F\(\\mathbf\{v\},\\mathbf\{x\}\_\{t\+1\}\)\-mF\(\\mathbf\{v\},\\mathbf\{x\}\)≥\\displaystyle\\geq\(1−1T\)​\(F​\(𝐯,𝐱t\)−m​F​\(𝐯,𝐱\)\)−L2​T2​D2\\displaystyle\(1\-\\frac\{1\}\{T\}\)\\left\(F\(\\mathbf\{v\},\\mathbf\{x\}\_\{t\}\)\-mF\(\\mathbf\{v\},\\mathbf\{x\}\)\\right\)\-\\frac\{L\}\{2T^\{2\}\}D^\{2\}Summing up the above inequalities overt=0,…,T−1t=0,\\ldots,T\-1, we obtain

F​\(𝐯,𝐱T\)−m​F​\(𝐯,𝐱\)\\displaystyle F\(\\mathbf\{v\},\\mathbf\{x\}\_\{T\}\)\-mF\(\\mathbf\{v\},\\mathbf\{x\}\)≥\\displaystyle\\geq\(1−1T\)T​\(F​\(𝐯,𝐱0\)−m​F​\(𝐯,𝐱∗\)\)−L2​T​D2\.\\displaystyle\(1\-\\frac\{1\}\{T\}\)^\{T\}\\left\(F\(\\mathbf\{v\},\\mathbf\{x\}\_\{0\}\)\-mF\(\\mathbf\{v\},\\mathbf\{x\}^\{\*\}\)\\right\)\-\\frac\{L\}\{2T\}D^\{2\}\.Furthermore, by choosing𝐱=𝐱∗=arg⁡max𝐱∈𝒳⁡F​\(𝐯,𝐱\)\\mathbf\{x\}=\\mathbf\{x\}^\{\*\}=\\arg\\max\_\{\\mathbf\{x\}\\in\\mathcal\{X\}\}F\(\\mathbf\{v\},\\mathbf\{x\}\), and combining with the non\-negativity ofFF, i\.e\.,F​\(𝐯,𝐱0\)≥0F\(\\mathbf\{v\},\\mathbf\{x\}\_\{0\}\)\\geq 0, we have

F​\(𝐯,𝐱T\)\\displaystyle F\(\\mathbf\{v\},\\mathbf\{x\}\_\{T\}\)≥m​\(1−\(1−1T\)T\)​F​\(𝐯,𝐱\)−L2​T​D2\\displaystyle\\geq m\\left\(1\-\(1\-\\frac\{1\}\{T\}\)^\{T\}\\right\)F\(\\mathbf\{v\},\\mathbf\{x\}\)\-\\frac\{L\}\{2T\}D^\{2\}≥m​\(1−1/e\)​F​\(𝐯,𝐱∗\)−L2​T​D2,\\displaystyle\\geq m\(1\-1/e\)F\(\\mathbf\{v\},\\mathbf\{x\}^\{\*\}\)\-\\frac\{L\}\{2T\}D^\{2\},where the last inequality follows from\(1−1/T\)T≥1/e\(1\-1/T\)^\{T\}\\geq 1/e\. Therefore, by settingT=𝒪​\(L​D2/ϵ\)T=\\mathcal\{O\}\(LD^\{2\}/\\epsilon\), we obtain the desired result\. ∎

Proof of Thm\.[2](https://arxiv.org/html/2606.11804#Thmtheorem2)

###### Proof\.

Firstly, we sum up all the inequalities in Eq\. \([7](https://arxiv.org/html/2606.11804#S4.E7)\) overkk, yielding the following

∑k=1K\[ϕ\(𝐯,𝐰k\+1,\{𝐱k\+1i\}\)−ϕ\(𝐯k,𝐰k\+1,\{𝐱k\+1i\}\]\\displaystyle\\sum^\{K\}\_\{k=1\}\\left\[\\phi\(\\mathbf\{v\},\\mathbf\{w\}\_\{k\+1\},\\\{\\mathbf\{x\}\_\{k\+1\}^\{i\}\\\}\)\-\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\+1\},\\\{\\mathbf\{x\}\_\{k\+1\}^\{i\}\\\}\\right\]≥\\displaystyle\\geq12​η​\(∥𝐯K−𝐯∥2−∥𝐯0−𝐯∥2\)−K​η​M22\\displaystyle\\frac\{1\}\{2\\eta\}\(\\lVert\\mathbf\{v\}\_\{K\}\-\\mathbf\{v\}\\rVert^\{2\}\-\\lVert\\mathbf\{v\}\_\{0\}\-\\mathbf\{v\}\\rVert^\{2\}\)\-\\frac\{K\\eta M^\{2\}\}\{2\}≥\\displaystyle\\geq−D𝒫2​η−K​η​M22,\\displaystyle\-\\frac\{D\_\{\\mathcal\{P\}\}\}\{2\\eta\}\-\\frac\{K\\eta M^\{2\}\}\{2\},\(11\)where the last inequality comes from the bound of𝒫\\mathcal\{P\}, i\.e\.,∥𝐯0−𝐯∥2≤D𝒫\\lVert\\mathbf\{v\}\_\{0\}\-\\mathbf\{v\}\\rVert^\{2\}\\leq D\_\{\\mathcal\{P\}\}for𝐯∈𝒫\\mathbf\{v\}\\in\\mathcal\{P\}\. Combining the constraint set of𝐰\\mathbf\{w\}with

ϕ​\(𝐯,𝐰,\{𝐱i\}\)=∑i=1I𝐰i​F​\(𝐯,𝐱i\),\\phi\(\\mathbf\{v\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)=\\sum^\{I\}\_\{i=1\}\\mathbf\{w\}\_\{i\}F\(\\mathbf\{v\},\\mathbf\{x\}^\{i\}\),we get them​\(1−1/e\)m\(1\-1/e\)\-approximate optimality ofF​\(𝐯,𝐱i\)F\(\\mathbf\{v\},\\mathbf\{x\}^\{i\}\)as demonstrated in Thm\.[1](https://arxiv.org/html/2606.11804#Thmtheorem1)\. It implies that\{𝐱i\}\\\{\\mathbf\{x\}^\{i\}\\\}satisfies∀𝐰\\forall\\mathbf\{w\}

ϕ​\(𝐯,𝐰,\{𝐱k\+1i\}\)≥m​\(1−1/e\)​max𝐱i∈𝒳i⁡ϕ​\(𝐯,𝐰,\{𝐱i\}\)−𝒪​\(L​D2T\)\.\\phi\(\\mathbf\{v\},\\mathbf\{w\},\\\{\\mathbf\{x\}\_\{k\+1\}^\{i\}\\\}\)\\geq m\(1\-1/e\)\\max\_\{\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\}\}\\phi\(\\mathbf\{v\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)\-\\mathcal\{O\}\(\\frac\{LD^\{2\}\}\{T\}\)\.\(12\)Following Step 3 in Alg\.[2](https://arxiv.org/html/2606.11804#alg2)and the inequality in Eq\. \([12](https://arxiv.org/html/2606.11804#A0.E12)\), we have

ϕ​\(𝐯k,𝐰k\+1,\{𝐱k\+1i\}\)=max𝐰∈𝒲⁡ϕ​\(𝐯k,𝐰,\{𝐱k\+1i\}\)\\displaystyle\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\}\_\{k\+1\},\\\{\\mathbf\{x\}\_\{k\+1\}^\{i\}\\\}\)=\\max\_\{\\mathbf\{w\}\\in\\mathcal\{W\}\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\},\\\{\\mathbf\{x\}\_\{k\+1\}^\{i\}\\\}\)≥\\displaystyle\\geqm​\(1−1/e\)​max𝐱i∈𝒳i,𝐰∈𝒲⁡ϕ​\(𝐯k,𝐰,\{𝐱i\}\)−𝒪​\(L​D2T\)\.\\displaystyle m\(1\-1/e\)\\max\_\{\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\},\\mathbf\{w\}\\in\\mathcal\{W\}\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)\-\\mathcal\{O\}\(\\frac\{LD^\{2\}\}\{T\}\)\.It follows from Eq\. \([11](https://arxiv.org/html/2606.11804#A0.E11)\) that

∑k=0K−1ϕ\(𝐯,𝐰k\+1,\{𝐱k\+1i\}\\displaystyle\\sum^\{K\-1\}\_\{k=0\}\\phi\(\\mathbf\{v\},\\mathbf\{w\}\_\{k\+1\},\\\{\\mathbf\{x\}\_\{k\+1\}^\{i\}\\\}−∑k=0K−1\[m​\(1−1/e\)​max𝐱i∈𝒳i,𝐰∈𝒲⁡ϕ​\(𝐯k,𝐰,\{𝐱i\}\)\]\\displaystyle\-\\sum^\{K\-1\}\_\{k=0\}\\left\[m\(1\-1/e\)\\max\_\{\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\},\\mathbf\{w\}\\in\\mathcal\{W\}\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)\\right\]≥\\displaystyle\\geq−D𝒫2​η−K​η​M22−K×𝒪​\(L​D2T\),\\displaystyle\-\\frac\{D\_\{\\mathcal\{P\}\}\}\{2\\eta\}\-\\frac\{K\\eta M^\{2\}\}\{2\}\-K\\times\\mathcal\{O\}\(\\frac\{LD^\{2\}\}\{T\}\),which holds for all𝐯∈𝒫\\mathbf\{v\}\\in\\mathcal\{P\}\. In the following, we chooseη=1K\\eta=\\frac\{1\}\{\\sqrt\{K\}\}and divide both sides byKK,

1K​∑k=0K−1ϕ​\(𝐯,𝐰k\+1,\{𝐱k\+1i\}\)\\displaystyle\\frac\{1\}\{K\}\\sum^\{K\-1\}\_\{k=0\}\\phi\(\\mathbf\{v\},\\mathbf\{w\}\_\{k\+1\},\\\{\\mathbf\{x\}\_\{k\+1\}^\{i\}\\\}\)−m​\(1−1/e\)​1K​∑k=0K−1\[max𝐱i∈𝒳i,𝐰∈𝒲⁡ϕ​\(𝐯k,𝐰,\{𝐱i\}\)\]\\displaystyle\-m\(1\-1/e\)\\frac\{1\}\{K\}\\sum^\{K\-1\}\_\{k=0\}\\left\[\\max\_\{\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\},\\mathbf\{w\}\\in\\mathcal\{W\}\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)\\right\]≥\\displaystyle\\geq−D𝒫K\+M2K−𝒪​\(L​D2T\)\.\\displaystyle\-\\frac\{D\_\{\\mathcal\{P\}\}\}\{\\sqrt\{K\}\}\+\\frac\{M^\{2\}\}\{\\sqrt\{K\}\}\-\\mathcal\{O\}\(\\frac\{LD^\{2\}\}\{T\}\)\.Then, combining with the convexity ofϕ​\(⋅,𝐰,\{𝐱i\}\)\\phi\(\\cdot,\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\), we have

1K​∑k=0K−1ϕ​\(𝐯k,𝐰,\{𝐱i\}\)≥ϕ​\(1K​∑k=0K−1𝐯k,𝐰,\{𝐱i\}\)\.\\displaystyle\\frac\{1\}\{K\}\\sum^\{K\-1\}\_\{k=0\}\\phi\(\\mathbf\{v\}\_\{k\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)\\geq\\phi\(\\frac\{1\}\{K\}\\sum^\{K\-1\}\_\{k=0\}\\mathbf\{v\}\_\{k\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)\.So we get

1K​∑k=0K−1ϕ​\(𝐯,𝐰k\+1,\{𝐱k\+1i\}\)\\displaystyle\\frac\{1\}\{K\}\\sum^\{K\-1\}\_\{k=0\}\\phi\(\\mathbf\{v\},\\mathbf\{w\}\_\{k\+1\},\\\{\\mathbf\{x\}\_\{k\+1\}^\{i\}\\\}\)−m​\(1−1/e\)​max𝐱i∈𝒳i,𝐰∈𝒲⁡ϕ​\(1K​∑k=0K−1𝐯k,𝐰,\{𝐱i\}\)\\displaystyle\-m\(1\-1/e\)\\max\_\{\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\},\\mathbf\{w\}\\in\\mathcal\{W\}\}\\phi\(\\frac\{1\}\{K\}\\sum^\{K\-1\}\_\{k=0\}\\mathbf\{v\}\_\{k\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)≥\\displaystyle\\geq−D𝒫K\+M2K−𝒪​\(L​D2T\),\\displaystyle\-\\frac\{D\_\{\\mathcal\{P\}\}\}\{\\sqrt\{K\}\}\+\\frac\{M^\{2\}\}\{\\sqrt\{K\}\}\-\\mathcal\{O\}\(\\frac\{LD^\{2\}\}\{T\}\),which holds for all𝐯∈𝒫\\mathbf\{v\}\\in\\mathcal\{P\}\. Observing

max𝐰∈𝒲,𝐱i∈𝒳i⁡ϕ​\(𝐯,𝐰,\{𝐱i\}\)≥ϕ​\(𝐯,𝐰k\+1,\{𝐱k\+1i\}\),\\max\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\}\}\\phi\(\\mathbf\{v\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)\\geq\\phi\(\\mathbf\{v\},\\mathbf\{w\}\_\{k\+1\},\\\{\\mathbf\{x\}\_\{k\+1\}^\{i\}\\\}\),and choosing𝐯=arg⁡min𝐯⁡ϕ​\(𝐯,𝐰,\{𝐱i\}\)\\mathbf\{v\}=\\arg\\min\_\{\\mathbf\{v\}\}\\phi\(\\mathbf\{v\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\), we obtain

min𝐯∈𝒫⁡max𝐰∈𝒲,𝐱i∈𝒳i⁡ϕ​\(𝐯,𝐰,\{𝐱i\}\)\\displaystyle\\min\_\{\\mathbf\{v\}\\in\\mathcal\{P\}\}\\max\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\}\}\\phi\(\\mathbf\{v\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)−m​\(1−1/e\)​max𝐰∈𝒲,𝐱i∈𝒳i⁡ϕ​\(𝐯¯,𝐰,\{𝐱i\}\)\\displaystyle\-m\(1\-1/e\)\\max\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\}\}\\phi\(\\bar\{\\mathbf\{v\}\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)≥\\displaystyle\\geq−D𝒫K\+M2K−𝒪​\(L​D2T\),\\displaystyle\-\\frac\{D\_\{\\mathcal\{P\}\}\}\{\\sqrt\{K\}\}\+\\frac\{M^\{2\}\}\{\\sqrt\{K\}\}\-\\mathcal\{O\}\(\\frac\{LD^\{2\}\}\{T\}\),where𝐯¯=1K​∑k=0K−1𝐯k\\bar\{\\mathbf\{v\}\}=\\frac\{1\}\{K\}\\sum^\{K\-1\}\_\{k=0\}\\mathbf\{v\}\_\{k\}\. Furthermore, with

K=𝒪​\(D𝒫/ϵ2\),T=𝒪​\(L​D2/ϵ\),K=\\mathcal\{O\}\(D\_\{\\mathcal\{P\}\}/\\epsilon^\{2\}\),\\qquad T=\\mathcal\{O\}\(LD^\{2\}/\{\\epsilon\}\),the output of Alg\.[2](https://arxiv.org/html/2606.11804#alg2),𝐯¯\\bar\{\\mathbf\{v\}\}satisfies

m​\(1−1/e\)​maxw∈𝒲,𝐱i∈𝒳i⁡ϕ​\(𝐯¯,𝐰,\{𝐱i\}\)≤OPTm​i​n​m​a​x\+ϵ,m\(1\-1/e\)\\max\_\{w\\in\\mathcal\{W\},\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\}\}\\phi\(\\bar\{\\mathbf\{v\}\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)\\leq\{\\rm OPT\}\_\{minmax\}\+\\epsilon,where

OPTminmax=min𝐯∈𝒫⁡max𝐰∈𝒲,𝐱i∈𝒳i⁡ϕ​\(𝐯,𝐰,\{𝐱i\}\)\.\{\\rm OPT\}\_\{\\rm minmax\}=\\min\_\{\\mathbf\{v\}\\in\\mathcal\{P\}\}\\max\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\mathbf\{x\}^\{i\}\\in\\mathcal\{X\}\_\{i\}\}\\phi\(\\mathbf\{v\},\\mathbf\{w\},\\\{\\mathbf\{x\}^\{i\}\\\}\)\.This means the output𝐯¯\\bar\{\\mathbf\{v\}\}is an\(α,ϵ\)\(\\alpha,\\epsilon\)\-approximation minmax solution withα=m​\(1−1/e\)\\alpha=m\(1\-1/e\)for adversarial sample generation across multiple submodular models\. ∎

### \-CProofs for Sec\.[V](https://arxiv.org/html/2606.11804#S5)

#### \-C1Auxiliary Properties ofGGandΦ\\Phi

Under Assumption[2](https://arxiv.org/html/2606.11804#Thmassumption2), the functionG​\(⋅,𝐰,\{𝐯j\}\)G\(\\cdot,\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)ismm\-weakly monotone and DR\-submodular\. The gradients ofG​\(𝐱,𝐰,\{𝐯j\}\)G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)w\.r\.t\.𝐰\\mathbf\{w\}and𝐱\\mathbf\{x\}can be computed as follows:

∇wG​\(𝐱,𝐰,\{𝐯j\}\)=∑j=1Jej​F​\(𝐱,𝐯j\)\+γ​\(𝐰−𝟏J\),\\displaystyle\\nabla\_\{w\}G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)=\\sum^\{J\}\_\{j=1\}e\_\{j\}F\(\\mathbf\{x\},\\mathbf\{v\}^\{j\}\)\+\\gamma\(\\mathbf\{w\}\-\\frac\{\\mathbf\{1\}\}\{J\}\),∇𝐱G​\(𝐱,𝐰,\{𝐯j\}\)=∑j=1J𝐰j​∇𝐱F​\(𝐱,𝐯j\)\.\\displaystyle\\nabla\_\{\\mathbf\{x\}\}G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)=\\sum^\{J\}\_\{j=1\}\\mathbf\{w\}\_\{j\}\\nabla\_\{\\mathbf\{x\}\}F\(\\mathbf\{x\},\\mathbf\{v\}^\{j\}\)\.This implies thatG​\(𝐱,𝐰,\{𝐯j\}\)G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)isLL\-smooth and hence the following inequality holds:

∥∇xG​\(𝐱,𝐰,\{𝐯1j\}\)−∇𝐱G​\(𝐱,𝐰,\{𝐯2j\}\)∥\\displaystyle\\lVert\\nabla\_\{x\}G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}\_\{1\}^\{j\}\\\}\)\-\\nabla\_\{\\mathbf\{x\}\}G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}\_\{2\}^\{j\}\\\}\)\\rVert=\\displaystyle=∑j=1Jwj​∥∇xF​\(𝐱,𝐯1j\)−∇𝐱F​\(𝐱,𝐯2j\)∥\\displaystyle\\sum^\{J\}\_\{j=1\}w\_\{j\}\\lVert\\nabla\_\{x\}F\(\\mathbf\{x\},\\mathbf\{v\}\_\{1\}^\{j\}\)\-\\nabla\_\{\\mathbf\{x\}\}F\(\\mathbf\{x\},\\mathbf\{v\}\_\{2\}^\{j\}\)\\rVert≤\\displaystyle\\leq∑j=1J𝐰j​∥𝐯1j−𝐯2j∥\\displaystyle\\sum^\{J\}\_\{j=1\}\\mathbf\{w\}\_\{j\}\\lVert\\mathbf\{v\}^\{j\}\_\{1\}\-\\mathbf\{v\}^\{j\}\_\{2\}\\rVert≤\\displaystyle\\leqmaxj∈\[J\]⁡∥𝐯1j−𝐯2j∥,\\displaystyle\\max\_\{j\\in\[J\]\}\\lVert\\mathbf\{v\}^\{j\}\_\{1\}\-\\mathbf\{v\}^\{j\}\_\{2\}\\rVert,\(13\)where the last inequality follows from the fact that the sum of𝐰j\\mathbf\{w\}\_\{j\}overjjis equal to11, as required by the constraint set𝒲\\mathcal\{W\}\.

To begin with, we define

Φ​\(𝐱\)​=def​min𝐰∈𝒲,𝐯j∈𝒫j⁡G​\(𝐱,𝐰,\{𝐯j\}\)\\displaystyle\\Phi\(\\mathbf\{x\}\)\\overset\{\\mathrm\{def\}\}\{=\}\\min\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\mathbf\{v\}^\{j\}\\in\\mathcal\{P\}\_\{j\}\}G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)\(14\)and let\(𝐰∗​\(𝐱\),\{𝐯j∗​\(𝐱\)\}\)=arg⁡min𝐰∈𝒲,𝐯j∈𝒫j⁡Φ​\(𝐱\)\(\\mathbf\{w\}^\{\*\}\(\\mathbf\{\\mathbf\{x\}\}\),\\\{\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\)\\\}\)=\\arg\\min\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\mathbf\{v\}^\{j\}\\in\\mathcal\{P\}\_\{j\}\}\\Phi\(\\mathbf\{x\}\)\. We can easily obtain the following properties regardingΦ​\(𝐱\)\\Phi\(\\mathbf\{x\}\)\. Since the proof is similar to that of Lemma 4\.3 in\[[14](https://arxiv.org/html/2606.11804#bib.bib38)\], we omit it here\.

###### Lemma 5\.

Under Assumption[2](https://arxiv.org/html/2606.11804#Thmassumption2), we have:

- •the gradient ofΦ\\Phiis ∇Φ​\(𝐱\)=∇𝐱G​\(𝐱,𝐰∗​\(𝐱\),\{𝐯j∗​\(𝐱\)\}\),\\nabla\\Phi\(\\mathbf\{x\}\)=\\nabla\_\{\\mathbf\{x\}\}G\(\\mathbf\{x\},\\mathbf\{w\}^\{\*\}\(\\mathbf\{x\}\),\\\{\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\)\\\}\),and the functionΦ​\(𝐱\)\\Phi\(\\mathbf\{x\}\)isLΦL\_\{\\Phi\}\-smooth, whereLΦ=\(L\+L2μ\)L\_\{\\Phi\}=\(L\+\\frac\{L^\{2\}\}\{\\mu\}\)\.
- •Define𝐰∗​\(𝐯\)=arg⁡min𝐰∈𝒲⁡G​\(𝐱,𝐰,\{𝐯j\}\)\\mathbf\{w\}^\{\*\}\(\\mathbf\{v\}\)=\\arg\\min\_\{\\mathbf\{w\}\\in\\mathcal\{W\}\}G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)with fixed𝐱\\mathbf\{x\}, the optimal solution𝐰∗​\(𝐯\)\\mathbf\{w\}^\{\*\}\(\\mathbf\{v\}\)isLμ\\frac\{L\}\{\\mu\}\-Lipschitz continuous: ∥𝐰∗​\(𝐯1\)−𝐰∗​\(𝐯2\)∥≤Lμ​maxj∈\[J\]⁡∥𝐯1j−𝐯2j∥,\\lVert\\mathbf\{w\}^\{\*\}\(\\mathbf\{v\}\_\{1\}\)\-\\mathbf\{w\}^\{\*\}\(\\mathbf\{v\}\_\{2\}\)\\rVert\\leq\\frac\{L\}\{\\mu\}\\max\_\{j\\in\[J\]\}\\lVert\\mathbf\{v\}^\{j\}\_\{1\}\-\\mathbf\{v\}^\{j\}\_\{2\}\\rVert,where𝐯\\mathbf\{v\}denotes the set of variables\{𝐯j\}\\\{\\mathbf\{v\}^\{j\}\\\}\.

Under Assumption[2](https://arxiv.org/html/2606.11804#Thmassumption2)and with the step sizeη=1/L\\eta=1/Lin Alg\.[3](https://arxiv.org/html/2606.11804#alg3), we have the following inequality according to the strongly convex with respect to𝐯j\\mathbf\{v\}^\{j\}, which states that the iteration𝐯Tj​\(𝐱k\)\\mathbf\{v\}^\{j\}\_\{T\}\(\\mathbf\{x\}\_\{k\}\)satisfies

∥𝐯Tj​\(𝐱k\)−𝐯j∗​\(𝐱k\)∥≤\(1−μL\)T/2​D𝒫j,\\lVert\\mathbf\{v\}^\{j\}\_\{T\}\(\\mathbf\{x\}\_\{k\}\)\-\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\)\\rVert\\leq\(1\-\\frac\{\\mu\}\{L\}\)^\{T/2\}D\_\{\\mathcal\{P\}\_\{j\}\},\(15\)where𝐯j∗​\(𝐱k\)=arg⁡min𝐯∈𝒫j⁡F​\(𝐱k,𝐯j​\(𝐱k\)\)\\mathbf\{v\}^\{j^\{\*\}\}\(\\mathbf\{x\}\_\{k\}\)=\\arg\\min\_\{\\mathbf\{v\}\\in\\mathcal\{P\}\_\{j\}\}F\(\\mathbf\{x\}\_\{k\},\\mathbf\{v\}^\{j\}\(\\mathbf\{x\}\_\{k\}\)\)\.

Similarly, sinceG​\(𝐱,𝐰,\{𝐯j\}\)G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)isγ\\gamma\-strongly convex andγ\\gamma\-smooth regarding𝐰\\mathbf\{w\}, the optimal vector𝐰∗​\(𝐱\)\\mathbf\{w\}^\{\*\}\(\\mathbf\{x\}\)can be determined exactly at each iteratekk\. The following lemma characterizes the relationship between the function values at two consecutive iteration points\.

###### Lemma 6\.

Let

Δk=∇Φ​\(𝐱k\)−∇G𝐱​\(𝐱k,𝐰∗​\(\{𝐯Tj\}k\),\{𝐯Tj​\(𝐱k\)\}\),\\Delta\_\{k\}=\\nabla\\Phi\(\\mathbf\{x\}\_\{k\}\)\-\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\),\\\{\\mathbf\{v\}\_\{T\}^\{j\}\(\\mathbf\{x\}\_\{k\}\)\\\}\),whereΦ\\Phiis defined as in Eq\. \([14](https://arxiv.org/html/2606.11804#A0.E14)\)\. Then, under Assumption[2](https://arxiv.org/html/2606.11804#Thmassumption2), the sequence\{𝐱k\}k≥1\\\{\\mathbf\{x\}\_\{k\}\\\}\_\{k\\geq 1\}generated by Alg\.[3](https://arxiv.org/html/2606.11804#alg3)satisfies the following inequality:

Φ​\(𝐱k\+1\)−Φ​\(𝐱k\)\\displaystyle\\Phi\(\\mathbf\{x\}\_\{k\+1\}\)\-\\Phi\(\\mathbf\{x\}\_\{k\}\)≥\\displaystyle\\geq1K​\(m​Φ​\(𝐱∗\)−Φ​\(𝐱k\)−2​D𝒳​∥Δk∥−LΦ2​K​D𝒳2\),\\displaystyle\\frac\{1\}\{K\}\\left\(m\\Phi\(\\mathbf\{x\}^\{\*\}\)\-\\Phi\(\\mathbf\{x\}\_\{k\}\)\-2D\_\{\\mathcal\{X\}\}\\lVert\\Delta\_\{k\}\\rVert\-\\frac\{L\_\{\\Phi\}\}\{2K\}D\_\{\\mathcal\{X\}\}^\{2\}\\right\),where𝐱∗\\mathbf\{x\}^\{\*\}is an optimal solution,LϕL\_\{\\phi\}is the smoothness parameter ofϕ​\(𝐱\)\\phi\(\\mathbf\{x\}\), andD𝒳D\_\{\\mathcal\{X\}\}is the diameter of the constraint set𝒳\\mathcal\{X\}\.

###### Proof\.

We begin the proof by leveraging theLΦL\_\{\\Phi\}\-smoothness ofΦ​\(𝐱\)\\Phi\(\\mathbf\{x\}\)and

∇Φ​\(𝐱k\)=∇G𝐱​\(𝐱k,𝐰∗​\(\{𝐯Tj\}k\),\{𝐯j∗​\(𝐱k\)\}\)\\nabla\\Phi\(\\mathbf\{x\}\_\{k\}\)=\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\),\\\{\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)as stated in Lem\.[5](https://arxiv.org/html/2606.11804#Thmlemma5), it holds

Φ​\(𝐱k\+1\)−Φ​\(𝐱k\)\\displaystyle\\Phi\(\\mathbf\{x\}\_\{k\+1\}\)\-\\Phi\(\\mathbf\{x\}\_\{k\}\)≥\\displaystyle\\geq⟨∇Φ​\(𝐱k\),𝐱k\+1−𝐱k⟩−LΦ2​∥𝐱k\+1−𝐱k∥22\\displaystyle\\left\\langle\\nabla\\Phi\(\\mathbf\{x\}\_\{k\}\),\\mathbf\{x\}\_\{k\+1\}\-\\mathbf\{x\}\_\{k\}\\right\\rangle\-\\frac\{L\_\{\\Phi\}\}\{2\}\\lVert\\mathbf\{x\}\_\{k\+1\}\-\\mathbf\{x\}\_\{k\}\\rVert^\{2\}\_\{2\}≥\\displaystyle\\geq⟨∇Φ​\(𝐱k\),𝐱k\+1−𝐱k⟩−LΦ2​∥𝐱k\+1−𝐱k∥22\\displaystyle\\left\\langle\\nabla\\Phi\(\\mathbf\{x\}\_\{k\}\),\\mathbf\{x\}\_\{k\+1\}\-\\mathbf\{x\}\_\{k\}\\right\\rangle\-\\frac\{L\_\{\\Phi\}\}\{2\}\\lVert\\mathbf\{x\}\_\{k\+1\}\-\\mathbf\{x\}\_\{k\}\\rVert^\{2\}\_\{2\}=\\displaystyle=1K​⟨∇Φ​\(𝐱k\),𝐝k⟩−LΦ2​K2​∥𝐝k∥22\\displaystyle\\frac\{1\}\{K\}\\left\\langle\\nabla\\Phi\(\\mathbf\{x\}\_\{k\}\),\\mathbf\{d\}\_\{k\}\\right\\rangle\-\\frac\{L\_\{\\Phi\}\}\{2K^\{2\}\}\\lVert\\mathbf\{d\}\_\{k\}\\rVert^\{2\}\_\{2\}\(16\)=\\displaystyle=1K​⟨∇G𝐱​\(𝐱k,𝐰∗​\(\{𝐯Tj\}k\),\{𝐯Tj​\(𝐱k\)\}\),𝐝k⟩\\displaystyle\\frac\{1\}\{K\}\\left\\langle\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\),\\\{\\mathbf\{v\}\_\{T\}^\{j\}\(\\mathbf\{x\}\_\{k\}\)\\\}\),\\mathbf\{d\}\_\{k\}\\right\\rangle\+1K​⟨Δk,𝐝k⟩−LΦ2​K2​∥𝐝k∥22\\displaystyle\+\\frac\{1\}\{K\}\\left\\langle\\Delta\_\{k\},\\mathbf\{d\}\_\{k\}\\right\\rangle\-\\frac\{L\_\{\\Phi\}\}\{2K^\{2\}\}\\lVert\\mathbf\{d\}\_\{k\}\\rVert^\{2\}\_\{2\}=\\displaystyle=1K​⟨\[∇G𝐱​\(𝐱k\)\]\+,𝐝k⟩\+1K​⟨Δk,𝐝k⟩−LΦ2​K2​∥𝐝k∥22\\displaystyle\\frac\{1\}\{K\}\\left\\langle\[\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\}\)\]\_\{\+\},\\mathbf\{d\}\_\{k\}\\right\\rangle\+\\frac\{1\}\{K\}\\left\\langle\\Delta\_\{k\},\\mathbf\{d\}\_\{k\}\\right\\rangle\-\\frac\{L\_\{\\Phi\}\}\{2K^\{2\}\}\\lVert\\mathbf\{d\}\_\{k\}\\rVert^\{2\}\_\{2\}≥\\displaystyle\\geq1K​⟨\[∇G𝐱​\(𝐱k\)\]\+,𝐱∗⟩\+1K​⟨Δk,𝐝k⟩−LΦ2​K2​∥𝐝k∥22\\displaystyle\\frac\{1\}\{K\}\\left\\langle\[\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\}\)\]\_\{\+\},\\mathbf\{x\}^\{\*\}\\right\\rangle\+\\frac\{1\}\{K\}\\left\\langle\\Delta\_\{k\},\\mathbf\{d\}\_\{k\}\\right\\rangle\-\\frac\{L\_\{\\Phi\}\}\{2K^\{2\}\}\\lVert\\mathbf\{d\}\_\{k\}\\rVert^\{2\}\_\{2\}\(17\)=\\displaystyle=1K​⟨\[∇Φ​\(𝐱k\)\]\+,𝐱∗⟩\+1K​\(⟨Δk,𝐝k⟩−⟨Δ¯k,𝐱∗⟩\)\\displaystyle\\frac\{1\}\{K\}\\left\\langle\[\\nabla\\Phi\(\\mathbf\{x\}\_\{k\}\)\]\_\{\+\},\\mathbf\{x\}^\{\*\}\\right\\rangle\+\\frac\{1\}\{K\}\\left\(\\langle\\Delta\_\{k\},\\mathbf\{d\}\_\{k\}\\rangle\-\\langle\\bar\{\\Delta\}\_\{k\},\\mathbf\{x\}^\{\*\}\\rangle\\right\)−LΦ2​K2​∥𝐝k∥22,\\displaystyle\-\\frac\{L\_\{\\Phi\}\}\{2K^\{2\}\}\\lVert\\mathbf\{d\}\_\{k\}\\rVert^\{2\}\_\{2\},where Eq\. \([16](https://arxiv.org/html/2606.11804#A0.E16)\) holds following Step 7 of Alg\.[3](https://arxiv.org/html/2606.11804#alg3), Eq\. \([17](https://arxiv.org/html/2606.11804#A0.E17)\) follows Step 6 of Alg\.[3](https://arxiv.org/html/2606.11804#alg3), the second equality holds sinceΔk=∇Φ​\(𝐱k\)−∇G𝐱​\(𝐱k,𝐰∗​\(\{𝐯Tj\}k\),\{𝐯Tj​\(𝐱k\)\}\)\\Delta\_\{k\}=\\nabla\\Phi\(\\mathbf\{x\}\_\{k\}\)\-\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\),\\\{\\mathbf\{v\}\_\{T\}^\{j\}\(\\mathbf\{x\}\_\{k\}\)\\\}\), and the third equality is due to Eq\. \([8](https://arxiv.org/html/2606.11804#S5.E8)\)\. Moreover, the second inequality comes from the linear maximization in Step 6, i\.e\.,

⟨\[∇G𝐱​\(𝐱k\)\]\+,𝐝k⟩≥⟨\[∇G𝐱​\(𝐱k\)\]\+,𝐱∗⟩,\\langle\[\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\}\)\]\_\{\+\},\\mathbf\{d\}\_\{k\}\\rangle\\geq\\langle\[\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\}\)\]\_\{\+\},\\mathbf\{x\}^\{\*\}\\rangle,where

𝐱∗​=def​arg⁡max𝐱∈𝒳⁡Φ​\(𝐱\)=arg⁡max𝐱∈𝒳⁡min𝐰∈𝒲,𝐯j∈𝒫j⁡G​\(𝐱,𝐰,\{𝐯j\}\)\.\\mathbf\{x\}^\{\*\}\\overset\{\\mathrm\{def\}\}\{=\}\\arg\\max\_\{\\mathbf\{x\}\\in\\mathcal\{X\}\}\\Phi\(\\mathbf\{x\}\)=\\arg\\max\_\{\\mathbf\{x\}\\in\\mathcal\{X\}\}\\min\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\mathbf\{v\}^\{j\}\\in\\mathcal\{P\}\_\{j\}\}G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)\.The last inequality is from𝐱∗≥𝟎\\mathbf\{x\}^\{\*\}\\geq\\mathbf\{0\}, and theΔ¯k\\bar\{\\Delta\}\_\{k\}in the last equality is defined as

Δ¯k=\[∇Φ​\(𝐱k\)\]\+−\[∇G𝐱​\(𝐱k,𝐰∗​\(\{𝐯Tj\}k\),\{𝐯Tj​\(𝐱k\)\}\)\]\+\.\\bar\{\\Delta\}\_\{k\}=\[\\nabla\\Phi\(\\mathbf\{x\}\_\{k\}\)\]\_\{\+\}\-\[\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\),\\\{\\mathbf\{v\}\_\{T\}^\{j\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)\]\_\{\+\}\.Then, focusing on the first term on the right\-hand side of Inequality \([17](https://arxiv.org/html/2606.11804#A0.E17)\), we obtain from the DR\-submodular ofF​\(𝐱,𝐯j∗​\(𝐱\)\)F\(\\mathbf\{x\},\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\)\)

⟨\[∇Φ​\(𝐱k\)\]\+,𝐱∗⟩\\displaystyle\\langle\[\\nabla\\Phi\(\\mathbf\{x\}\_\{k\}\)\]\_\{\+\},\\mathbf\{x\}^\{\*\}\\rangle≥\\displaystyle\\geq⟨\[∇Φ​\(𝐱k\)\]\+,𝐱∗∨𝐱k−𝐱k⟩\\displaystyle\\langle\[\\nabla\\Phi\(\\mathbf\{x\}\_\{k\}\)\]\_\{\+\},\\mathbf\{x\}^\{\*\}\\vee\\mathbf\{x\}\_\{k\}\-\\mathbf\{x\}\_\{k\}\\rangle≥\\displaystyle\\geq⟨∇G𝐱​\(𝐱k,𝐰∗​\(𝐱k\),\{𝐯j∗​\(𝐱k\)\}\),𝐱∗∨𝐱k−𝐱k⟩\\displaystyle\\langle\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\),\\\{\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\)\\\}\),\\mathbf\{x\}^\{\*\}\\vee\\mathbf\{x\}\_\{k\}\-\\mathbf\{x\}\_\{k\}\\rangle≥\\displaystyle\\geqG​\(𝐱∗∨𝐱k,𝐰∗​\(𝐱k\),\{𝐯j∗​\(𝐱k\)\}\)−G​\(𝐱k,𝐰∗​\(𝐱k\),\{𝐯j∗​\(𝐱k\)\}\)\\displaystyle G\(\\mathbf\{x\}^\{\*\}\\vee\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\),\\\{\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)\-G\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\),\\\{\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)≥\\displaystyle\\geqm​G​\(𝐱∗,𝐰∗​\(𝐱k\),\{𝐯j∗​\(𝐱k\)\}\)−G​\(𝐱k,𝐰∗​\(𝐱k\),\{𝐯j∗​\(𝐱k\)\}\)\\displaystyle mG\(\\mathbf\{x\}^\{\*\},\\mathbf\{w\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\),\\\{\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)\-G\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\),\\\{\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)≥\\displaystyle\\geqm​Φ​\(𝐱∗\)−Φ​\(𝐯k\)\.\\displaystyle m\\Phi\(\\mathbf\{x\}^\{\*\}\)\-\\Phi\(\\mathbf\{v\}\_\{k\}\)\.\(18\)Here, the first inequality follows from𝐱∗∨𝐱k≤𝐱∗\+𝐱k\\mathbf\{x\}^\{\*\}\\vee\\mathbf\{x\}\_\{k\}\\leq\\mathbf\{x\}^\{\*\}\+\\mathbf\{x\}\_\{k\}for𝐱∗,𝐱k∈𝒳\\mathbf\{x\}^\{\*\},\\mathbf\{x\}\_\{k\}\\in\\mathcal\{X\}, the second one comes from the definition ofΦ​\(𝐱\)\\Phi\(\\mathbf\{x\}\)in Lem\.[5](https://arxiv.org/html/2606.11804#Thmlemma5)and𝐱∗∨𝐱k−𝐱k≥𝟎\\mathbf\{x\}^\{\*\}\\vee\\mathbf\{x\}\_\{k\}\-\\mathbf\{x\}\_\{k\}\\geq\\mathbf\{0\}, the third inequality is obtained using the DR\-submodularity ofG​\(⋅,𝐰,\{𝐯j\}\)G\(\\cdot,\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)and Lem\.[10](https://arxiv.org/html/2606.11804#A0.E10)\(iii\) with𝐱∗∨𝐱k≥𝐱k\\mathbf\{x\}^\{\*\}\\vee\\mathbf\{x\}\_\{k\}\\geq\\mathbf\{x\}\_\{k\}, and the fourth follows from themm\-weak monotonicity ofG​\(⋅,𝐰,\{𝐯j\}\)G\(\\cdot,\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)as along with the fact

G​\(𝐱∗,𝐰∗​\(𝐱k\),\{𝐯j∗​\(𝐱k\)\}\)≥Φ​\(𝐱∗\),G\(\\mathbf\{x\}^\{\*\},\\mathbf\{w\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\),\\\{\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)\\geq\\Phi\(\\mathbf\{x\}^\{\*\}\),whereΦ​\(𝐱∗\)=max𝐱∈𝒳⁡min𝐰∈𝒲,𝐯j∈𝒫j⁡G​\(𝐱,𝐰,\{𝐯j\}\)\\Phi\(\\mathbf\{x\}^\{\*\}\)=\\max\_\{\\mathbf\{x\}\\in\\mathcal\{X\}\}\\min\_\{\\mathbf\{w\}\\in\\mathcal\{W\},\\mathbf\{v\}^\{j\}\\in\\mathcal\{P\}\_\{j\}\}G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)in the last inequality\. Combining Eqs\. \([17](https://arxiv.org/html/2606.11804#A0.E17)\) and \([18](https://arxiv.org/html/2606.11804#A0.E18)\), we obtain

Φ​\(𝐱k\+1\)−Φ​\(𝐱k\)\\displaystyle\\Phi\(\\mathbf\{x\}\_\{k\+1\}\)\-\\Phi\(\\mathbf\{x\}\_\{k\}\)≥\\displaystyle\\geq1K​\(m​Φ​\(𝐱∗\)−Φ​\(𝐱k\)\)\+1K​\(⟨Δk,𝐝k⟩−⟨Δ¯k,𝐱∗⟩\)\\displaystyle\\frac\{1\}\{K\}\(m\\Phi\(\\mathbf\{x\}^\{\*\}\)\-\\Phi\(\\mathbf\{x\}\_\{k\}\)\)\+\\frac\{1\}\{K\}\\left\(\\langle\\Delta\_\{k\},\\mathbf\{d\}\_\{k\}\\rangle\-\\langle\\bar\{\\Delta\}\_\{k\},\\mathbf\{x\}^\{\*\}\\rangle\\right\)−LΦ2​K2​∥𝐝k∥22\\displaystyle\-\\frac\{L\_\{\\Phi\}\}\{2K^\{2\}\}\\lVert\\mathbf\{d\}\_\{k\}\\rVert^\{2\}\_\{2\}≥\\displaystyle\\geq1K​\(m​Φ​\(𝐱∗\)−Φ​\(𝐱k\)\)−2​D𝒳K​∥Δk∥−LΦ2​K2​D𝒳2,\\displaystyle\\frac\{1\}\{K\}\(m\\Phi\(\\mathbf\{x\}^\{\*\}\)\-\\Phi\(\\mathbf\{x\}\_\{k\}\)\)\-\\frac\{2D\_\{\\mathcal\{X\}\}\}\{K\}\\lVert\\Delta\_\{k\}\\rVert\-\\frac\{L\_\{\\Phi\}\}\{2K^\{2\}\}D\_\{\\mathcal\{X\}\}^\{2\},where the second inequality holds by Cauchy\-Schwartz inequality, i\.e\.,

∥a∥​∥b∥≥⟨a,b⟩≥−∥a∥​∥b∥,\\lVert a\\rVert\\lVert b\\rVert\\geq\\langle a,b\\rangle\\geq\-\\lVert a\\rVert\\lVert b\\rVert,𝐝k,𝐱∗∈𝒳\\mathbf\{d\}\_\{k\},\\mathbf\{x\}^\{\*\}\\in\\mathcal\{X\}and∥Δ¯k∥≤∥Δk∥\\lVert\\bar\{\\Delta\}\_\{k\}\\rVert\\leq\\lVert\\Delta\_\{k\}\\rVert\.

In fact, for two setsA=\{i:\[∇Φ​\(𝐱k\)\]i≥0\}A=\\\{i:\[\\nabla\\Phi\(\\mathbf\{x\}\_\{k\}\)\]\_\{i\}\\geq 0\\\}andB=\{i:\[∇G𝐱​\(𝐱k,𝐰∗​\(\{𝐯Tj\}k\),\{𝐯Tj​\(𝐱k\)\}\)\]i≥0\}B=\\\{i:\[\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\),\\\{\\mathbf\{v\}\_\{T\}^\{j\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)\]\_\{i\}\\geq 0\\\}, it is obvious that

\|\[Δ¯k\]i\|​\{=\|\[Δk\]i\|,i∈A∩B≤\|\[Δk\]i\|,i∈A∪B−A∩B=0≤\[Δk\]i,Otherwise\\lvert\[\\bar\{\\Delta\}\_\{k\}\]\_\{i\}\\rvert\\begin\{cases\}=\\lvert\[\\Delta\_\{k\}\]\_\{i\}\\rvert,&i\\in A\\cap B\\\\ \\leq\\lvert\[\\Delta\_\{k\}\]\_\{i\}\\rvert,&i\\in A\\cup B\-A\\cap B\\\\ =0\\leq\[\\Delta\_\{k\}\]\_\{i\},&\\text\{Otherwise\}\\\\ \\end\{cases\}Thus, we have∥Δ¯k∥≤∥Δk∥\\lVert\\bar\{\\Delta\}\_\{k\}\\rVert\\leq\\lVert\\Delta\_\{k\}\\rVertand complete the proof\. ∎

#### \-C2Proof of Theorem[3](https://arxiv.org/html/2606.11804#Thmtheorem3)

Based on Lem\.[6](https://arxiv.org/html/2606.11804#Thmlemma6), we present the proof of Thm\.[3](https://arxiv.org/html/2606.11804#Thmtheorem3)as follows:

###### Proof\.

First, we bound∥Δk∥\\lVert\\Delta\_\{k\}\\rVerton the right hand side as follows

∥Δk∥=\\displaystyle\\lVert\\Delta\_\{k\}\\rVert=∥∇Φ​\(𝐱k\)−∇G𝐱​\(𝐱k,𝐰∗​\(\{𝐯Tj\}k\),\{𝐯Tj​\(𝐱k\)\}\)∥\\displaystyle\\lVert\\nabla\\Phi\(\\mathbf\{x\}\_\{k\}\)\-\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\),\\\{\\mathbf\{v\}\_\{T\}^\{j\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)\\rVert≤\\displaystyle\\leq∥∇𝐱G\(𝐱k,𝐰∗\(𝐱k\),\{𝐯j∗\(𝐱k\)\}\)\\displaystyle\\lVert\\nabla\_\{\\mathbf\{x\}\}G\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\),\\\{\\mathbf\{v\}^\{j^\{\*\}\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)−∇G𝐱\(𝐱k,𝐰∗\(𝐱k\),\{𝐯Tj\(𝐱k\)\}\)∥\\displaystyle\-\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\),\\\{\\mathbf\{v\}\_\{T\}^\{j\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)\\rVert\+∥∇G𝐱\(𝐱k,𝐰∗\(𝐱k\),\{𝐯Tj\(𝐱k\)\}\)\\displaystyle\+\\lVert\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\),\\\{\\mathbf\{v\}\_\{T\}^\{j\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)−∇G𝐱\(𝐱k,𝐰∗\(\{𝐯Tj\}k\),\{𝐯Tj\(𝐱k\)\}\)∥\\displaystyle\-\\nabla G\_\{\\mathbf\{x\}\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\),\\\{\\mathbf\{v\}\_\{T\}^\{j\}\(\\mathbf\{x\}\_\{k\}\)\\\}\)\\rVert≤\\displaystyle\\leqLmaxj∈\[J\]∥𝐯j∗\(𝐱k\)−𝐯Tj\(𝐱k\)\)∥\\displaystyle L\\max\_\{j\\in\[J\]\}\\lVert\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\)\-\\mathbf\{v\}\_\{T\}^\{j\}\(\\mathbf\{x\}\_\{k\}\)\)\\rVert\+γ​∥𝐰∗​\(xk\)−𝐰∗​\(\{𝐯Tj\}k\)∥\\displaystyle\+\\gamma\\lVert\\mathbf\{w\}^\{\*\}\(x\_\{k\}\)\-\\mathbf\{w\}^\{\*\}\(\\\{\\mathbf\{v\}^\{j\}\_\{T\}\\\}\_\{k\}\)\\rVert≤\\displaystyle\\leq\(L\+γLμ\)maxj∈\[J\]∥𝐯j∗\(𝐱k\)−𝐯Tj\(𝐱k\)\)∥\\displaystyle\(L\+\\gamma\\frac\{L\}\{\\mu\}\)\\max\_\{j\\in\[J\]\}\\lVert\{\\mathbf\{v\}^\{j\}\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\)\-\\mathbf\{v\}\_\{T\}^\{j\}\(\\mathbf\{x\}\_\{k\}\)\)\\rVert≤\\displaystyle\\leq\(L\+γ​Lμ\)​\(1−μL\)T/2​D𝒫,\\displaystyle\(L\+\\gamma\\frac\{L\}\{\\mu\}\)\(1\-\\frac\{\\mu\}\{L\}\)^\{T/2\}D\_\{\\mathcal\{P\}\},where the second inequality is derived based on combining the inequality in Eq\. \([13](https://arxiv.org/html/2606.11804#A0.E13)\) andγ\\gamma\-smoothness ofG​\(𝐱,𝐰,\{𝐯j\}\)G\(\\mathbf\{x\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j\}\\\}\)w\.r\.t\.𝐰\\mathbf\{w\}, the third inequality holds by combiningLμ\\frac\{L\}\{\\mu\}\-Lipschitz continuous of𝐰∗\\mathbf\{w\}^\{\*\}in Lem\.[5](https://arxiv.org/html/2606.11804#Thmlemma5)with

𝐰∗​\(𝐱k\)=arg⁡max𝐰∈𝒲⁡G​\(𝐱k,𝐰,\{𝐯j∗​\(𝐱k\)\}\),\\mathbf\{w\}^\{\*\}\(\\mathbf\{x\}\_\{k\}\)=\\arg\\max\_\{\\mathbf\{w\}\\in\\mathcal\{W\}\}G\(\\mathbf\{x\}\_\{k\},\\mathbf\{w\},\\\{\\mathbf\{v\}^\{j^\{\*\}\}\(\\mathbf\{x\}\_\{k\}\)\\\}\),and the last inequality follows from \([15](https://arxiv.org/html/2606.11804#A0.E15)\) andD𝒫=maxj⁡\{D𝒫j\}D\_\{\\mathcal\{P\}\}=\\max\_\{j\}\\\{D\_\{\\mathcal\{P\}\_\{j\}\}\\\}\.

Therefore, by settingQ=\(L\+γ​Lμ\)Q=\(L\+\\gamma\\frac\{L\}\{\\mu\}\)and rearranging the inequality in Lem\.[6](https://arxiv.org/html/2606.11804#Thmlemma6)through subtractingm​Φ​\(𝐱∗\)m\\Phi\(\\mathbf\{x\}^\{\*\}\)from both sides, we obtain

Φ​\(𝐱k\+1\)−m​Φ​\(𝐱∗\)≥\\displaystyle\\Phi\(\\mathbf\{x\}\_\{k\+1\}\)\-m\\Phi\(\\mathbf\{x\}^\{\*\}\)\\geq\(1−1K\)​\(Φ​\(𝐱k\)−m​Φ​\(𝐱∗\)\)\\displaystyle\(1\-\\frac\{1\}\{K\}\)\(\\Phi\(\\mathbf\{x\}\_\{k\}\)\-m\\Phi\(\\mathbf\{x\}^\{\*\}\)\)\(19\)−2​Q​D𝒫​D𝒳K​\(1−μL\)T/2−LΦ2​D𝒳22​K2\.\\displaystyle\-\\frac\{2QD\_\{\\mathcal\{P\}\}D\_\{\\mathcal\{X\}\}\}\{K\}\(1\-\\frac\{\\mu\}\{L\}\)^\{T/2\}\-\\frac\{L\_\{\\Phi\}^\{2\}D^\{2\}\_\{\\mathcal\{X\}\}\}\{2K^\{2\}\}\.Now, we telescope Eq\. \([19](https://arxiv.org/html/2606.11804#A0.E19)\) over all the iterations fork=0,…,K−1k=0,\\ldots,K\-1, which yields

Φ​\(𝐱K\)−m​Φ​\(𝐱∗\)≥\\displaystyle\\Phi\(\\mathbf\{x\}\_\{K\}\)\-m\\Phi\(\\mathbf\{x\}^\{\*\}\)\\geq\(1−1K\)K​\(Φ​\(𝐱0\)−m​Φ​\(𝐱∗\)\)\\displaystyle\(1\-\\frac\{1\}\{K\}\)^\{K\}\(\\Phi\(\\mathbf\{x\}\_\{0\}\)\-m\\Phi\(\\mathbf\{x\}^\{\*\}\)\)−∑k=0K−12​Q​D𝒫​D𝒳K​ρT/2−L2​D𝒳22​K\\displaystyle\-\\sum^\{K\-1\}\_\{k=0\}\\frac\{2QD\_\{\\mathcal\{P\}\}D\_\{\\mathcal\{X\}\}\}\{K\}\\rho^\{T/2\}\-\\frac\{L^\{2\}D^\{2\}\_\{\\mathcal\{X\}\}\}\{2K\}≥\\displaystyle\\geq\(1−1K\)K​\(Φ​\(𝐱0\)−m​Φ​\(𝐱∗\)\)\\displaystyle\(1\-\\frac\{1\}\{K\}\)^\{K\}\(\\Phi\(\\mathbf\{x\}\_\{0\}\)\-m\\Phi\(\\mathbf\{x\}^\{\*\}\)\)−2​Q​D𝒳​D𝒫​ρT/2−LΦ2​D𝒳22​K,\\displaystyle\-2QD\_\{\\mathcal\{X\}\}D\_\{\\mathcal\{P\}\}\\rho^\{T/2\}\-\\frac\{L\_\{\\Phi\}^\{2\}D^\{2\}\_\{\\mathcal\{X\}\}\}\{2K\},whereρ=1−μL\\rho=1\-\\frac\{\\mu\}\{L\}\. Furthermore, when

K≥LΦ2​D𝒳22​ϵandT≥2​logρ⁡ϵ2​Q​D𝒳​D𝒫,K\\geq\\frac\{L\_\{\\Phi\}^\{2\}D^\{2\}\_\{\\mathcal\{X\}\}\}\{2\\epsilon\}\\qquad\\text\{and\}\\qquad T\\geq 2\\log\_\{\\rho\}\\frac\{\\epsilon\}\{2QD\_\{\\mathcal\{X\}\}D\_\{\\mathcal\{P\}\}\},it holds that

Φ​\(𝐱K\)≥\\displaystyle\\Phi\(\\mathbf\{x\}\_\{K\}\)\\geqm​\(1−\(1−1K\)K\)​Φ​\(𝐱∗\)−ϵ\\displaystyle m\\left\(1\-\(1\-\\frac\{1\}\{K\}\)^\{K\}\\right\)\\Phi\(\\mathbf\{x\}^\{\*\}\)\-\\epsilon≥\\displaystyle\\geqm​\(1−1/e\)​Φ​\(𝐱∗\)−ϵ,\\displaystyle m\\left\(1\-1/e\\right\)\\Phi\(\\mathbf\{x\}^\{\*\}\)\-\\epsilon,where the second inequality is because ofΦ​\(𝐱0\)≥0\\Phi\(\\mathbf\{x\}\_\{0\}\)\\geq 0by definition and\(1−1K\)K≤1/e\(1\-\\frac\{1\}\{K\}\)^\{K\}\\leq 1/eby simple calculation\. ∎

### \-DAdditional Experimental Details and Results

#### \-D1Detailed Definitions of Evaluation Metrics

In this section, we provide the detailed definitions of the performance metrics used in the experiments\. Unless otherwise specified, all attacked solutions are evaluated under the original clean objective, following the shared evaluation protocol adopted in the main text\. For notational simplicity, we omit the explicit dependence of attacked solutions on\(p,ϵp,D\)\(p,\\epsilon\_\{p\},D\)when no confusion arises\.

##### Attack Metrics

Let𝐱T,i\\mathbf\{x\}\_\{T,i\}denote the clean\-reference solution produced by Alg\.[1](https://arxiv.org/html/2606.11804#alg1)for modeliiunder the original similarity structureΩi\\Omega\_\{i\}\. For an attack typep∈\{1,2,∞\}p\\in\\\{1,2,\\infty\\\}, attack budgetϵp\\epsilon\_\{p\}, and feasible\-set upper boundDD, let𝐱T,iatt\\mathbf\{x\}^\{\\rm att\}\_\{T,i\}denote the attacked solution obtained by applying Alg\.[1](https://arxiv.org/html/2606.11804#alg1)to the perturbed data\. We evaluate the attack effect under the clean objectiveF​\(⋅,Ωi\)F\(\\cdot,\\Omega\_\{i\}\)\.

Success Ratio of Attack\.We first define the degradation of modeliiunder attack as

Δiatt​\(p,ϵp,D\)=F​\(𝐱T,i,Ωi\)−F​\(𝐱T,iatt,Ωi\)\.\\Delta^\{\\rm att\}\_\{i\}\(p,\\epsilon\_\{p\},D\)=F\(\\mathbf\{x\}\_\{T,i\},\\Omega\_\{i\}\)\-F\(\\mathbf\{x\}^\{\\rm att\}\_\{T,i\},\\Omega\_\{i\}\)\.
A target model is regarded as successfully attacked if

Δiatt​\(p,ϵp,D\)≥0,\\Delta^\{\\rm att\}\_\{i\}\(p,\\epsilon\_\{p\},D\)\\geq 0,that is, the attacked solution yields no larger clean\-objective value than the clean\-reference solution\. Accordingly, the success ratio is defined as

Ratioatt​\(p,ϵp,D\)=1I​∑i=1I𝟏​\{Δiatt​\(p,ϵp,D\)≥0\}\.\\textbf\{Ratio\}^\{\\rm att\}\(p,\\epsilon\_\{p\},D\)=\\frac\{1\}\{I\}\\sum\_\{i=1\}^\{I\}\\mathbf\{1\}\\\!\\left\\\{\\Delta^\{\\rm att\}\_\{i\}\(p,\\epsilon\_\{p\},D\)\\geq 0\\right\\\}\.A larger value ofRatioatt​\(p,ϵp,D\)\\textbf\{Ratio\}^\{\\rm att\}\(p,\\epsilon\_\{p\},D\)indicates that the generated perturbation successfully degrades a larger fraction of target models\.

Average Degradation and Attack Intensity\.To measure the average attack effect over all target models, we define the average degradation as

Δ¯att​\(p,ϵp,D\)=1I​∑i=1I\(F​\(𝐱T,i,Ωi\)−F​\(𝐱T,iatt,Ωi\)\)\.\\bar\{\\Delta\}^\{\\rm att\}\(p,\\epsilon\_\{p\},D\)=\\frac\{1\}\{I\}\\sum\_\{i=1\}^\{I\}\\left\(F\(\\mathbf\{x\}\_\{T,i\},\\Omega\_\{i\}\)\-F\(\\mathbf\{x\}^\{\\rm att\}\_\{T,i\},\\Omega\_\{i\}\)\\right\)\.
Based on this quantity, we define the normalized attack intensity as

Intensityatt​\(p,ϵp,D\)=Δ¯att​\(p,ϵp,D\)1I​∑i=1IF​\(𝐱T,i,Ωi\)\.\\textbf\{Intensity\}^\{\\rm att\}\(p,\\epsilon\_\{p\},D\)=\\frac\{\\bar\{\\Delta\}^\{\\rm att\}\(p,\\epsilon\_\{p\},D\)\}\{\\frac\{1\}\{I\}\\sum\_\{i=1\}^\{I\}F\(\\mathbf\{x\}\_\{T,i\},\\Omega\_\{i\}\)\}\.
A larger value ofΔ¯att​\(p,ϵp,D\)\\bar\{\\Delta\}^\{\\rm att\}\(p,\\epsilon\_\{p\},D\)orIntensityatt​\(p,ϵp,D\)\\textbf\{Intensity\}^\{\\rm att\}\(p,\\epsilon\_\{p\},D\)indicates a stronger attack and hence greater vulnerability of the clean\-reference summarization solver\.

##### Defense Metrics

We use three metrics to evaluate the robust algorithm:Loss,Robustness, andMitigation\. Let𝐱T,irob\\mathbf\{x\}^\{\\rm rob\}\_\{T,i\}denote the solution produced by Alg\.[3](https://arxiv.org/html/2606.11804#alg3)under the clean setting, and let𝐱T,irob,att\\mathbf\{x\}^\{\\rm rob,att\}\_\{T,i\}denote the robust solution obtained under attack\. We continue to evaluate all quantities below under the clean objectiveF​\(⋅,Ωi\)F\(\\cdot,\\Omega\_\{i\}\)\.

Loss\.This metric measures the clean\-data utility loss caused by using the robust algorithm instead of the plain greedy algorithm\. It is defined as

𝐋𝐨𝐬𝐬=1I​∑i=1IF​\(𝐱T,i,Ωi\)−F​\(𝐱T,irob,Ωi\)F​\(𝐱T,i,Ωi\)\.\{\\bf Loss\}=\\frac\{1\}\{I\}\\sum\_\{i=1\}^\{I\}\\frac\{F\(\\mathbf\{x\}\_\{T,i\},\\Omega\_\{i\}\)\-F\(\\mathbf\{x\}^\{\\rm rob\}\_\{T,i\},\\Omega\_\{i\}\)\}\{F\(\\mathbf\{x\}\_\{T,i\},\\Omega\_\{i\}\)\}\.A smaller value ofLossindicates that the robust algorithm preserves the clean\-data utility more effectively\.

Robustness\.This metric measures the sensitivity of the robust solution to attacks by comparing the robust algorithm under clean and attacked settings\. It is defined as

𝐑𝐨𝐛𝐮𝐬𝐭𝐧𝐞𝐬𝐬=1I​∑i=1I\|F​\(𝐱T,irob,Ωi\)−F​\(𝐱T,irob,att,Ωi\)\|F​\(𝐱T,irob,Ωi\)\.\{\\bf Robustness\}=\\frac\{1\}\{I\}\\sum\_\{i=1\}^\{I\}\\frac\{\\left\|F\(\\mathbf\{x\}^\{\\rm rob\}\_\{T,i\},\\Omega\_\{i\}\)\-F\(\\mathbf\{x\}^\{\\rm rob,att\}\_\{T,i\},\\Omega\_\{i\}\)\\right\|\}\{F\(\\mathbf\{x\}^\{\\rm rob\}\_\{T,i\},\\Omega\_\{i\}\)\}\.A smaller value ofRobustnessindicates that the robust algorithm is more stable under attacks\.

Mitigation\.This metric measures how much the robust algorithm reduces the degradation caused by attacks, compared with the attacked greedy solution\. It is defined as

𝐌𝐢𝐭𝐢𝐠𝐚𝐭𝐢𝐨𝐧=1I​∑i=1IF​\(𝐱T,irob,att,Ωi\)−F​\(𝐱T,iatt,Ωi\)F​\(𝐱T,i,Ωi\)\.\{\\bf Mitigation\}=\\frac\{1\}\{I\}\\sum\_\{i=1\}^\{I\}\\frac\{F\(\\mathbf\{x\}^\{\\rm rob,att\}\_\{T,i\},\\Omega\_\{i\}\)\-F\(\\mathbf\{x\}^\{\\rm att\}\_\{T,i\},\\Omega\_\{i\}\)\}\{F\(\\mathbf\{x\}\_\{T,i\},\\Omega\_\{i\}\)\}\.A larger value ofMitigationindicates that the robust algorithm more effectively offsets the damage caused by attacks\. In particular, a positive value means that, on average, the robust algorithm achieves a better clean\-objective value under attack than the attacked greedy solution\.

##### Structural Metrics

For the controlled clustered benchmark, we further evaluate the structural quality of the rounded summary\. Let𝒞=\{C1,…,Cm\}\\mathcal\{C\}=\\\{C\_\{1\},\\ldots,C\_\{m\}\\\}be the set of ground\-truth clusters, and letHHdenote the set of designated hub representatives, with one hub representative for each cluster\. Given a rounded top\-kksummarySkS\_\{k\}, we report three structural metrics:Coverage,Hit, andRedundancy\.

Coverage\.Coverage measures the fraction of ground\-truth clusters represented by the selected summary\. It is defined as

Cov​\(Sk\)=\|\{c:Sk∩Cc≠∅\}\|m\.\\mathrm\{Cov\}\(S\_\{k\}\)=\\frac\{\|\\\{c:S\_\{k\}\\cap C\_\{c\}\\neq\\emptyset\\\}\|\}\{m\}\.A larger value ofCov​\(Sk\)\\mathrm\{Cov\}\(S\_\{k\}\)indicates that the selected summary covers more clusters and is therefore more representative at the cluster level\.

Hit\.Hit measures whether the selected summary contains the designated hub representatives\. It is defined as

Hit​\(Sk\)=\|Sk∩H\|m\.\\mathrm\{Hit\}\(S\_\{k\}\)=\\frac\{\|S\_\{k\}\\cap H\|\}\{m\}\.A larger value ofHit​\(Sk\)\\mathrm\{Hit\}\(S\_\{k\}\)indicates that the summary selects more true hub representatives\.

Redundancy\.Redundancy measures repeated selection within already covered clusters\. It is defined as

Red​\(Sk\)=1−\|\{c:Sk∩Cc≠∅\}\|k\.\\mathrm\{Red\}\(S\_\{k\}\)=1\-\\frac\{\|\\\{c:S\_\{k\}\\cap C\_\{c\}\\neq\\emptyset\\\}\|\}\{k\}\.A smaller value ofRed​\(Sk\)\\mathrm\{Red\}\(S\_\{k\}\)indicates that the selected summary contains less repeated information from the same clusters\. Therefore, higher Coverage and Hit values and lower Redundancy values correspond to better structural summary quality\.

##### Downstream Metrics

For the controlled clustered benchmark, we further evaluate whether the rounded summary remains useful for downstream classification\. Each cluster is treated as one class, and the selected top\-kksummarySkS\_\{k\}is used as a small training set\. All downstream evaluation is performed on clean test samples under the clean similarity matrix, so that the reported performance reflects the usefulness of the selected summary rather than a change in the test distribution\. We report two downstream metrics:NN Acc\.andRecovery\.

NN Acc\.NN Acc\. denotes nearest\-neighbor classification accuracy\. For each clean test sample, we assign the label of the most similar selected summary item under the clean similarity matrix\. The resulting classification accuracy is reported as NN Acc\. A larger value of NN Acc\. indicates that the selected summary is more useful for downstream classification\.

Recovery\.Recovery measures the fraction of downstream accuracy loss recovered relative to the attacked summary\. It is defined as

Recovery=Accmethod−AccattackAccclean−Accattack\.\\mathrm\{Recovery\}=\\frac\{\\mathrm\{Acc\}\_\{\\mathrm\{method\}\}\-\\mathrm\{Acc\}\_\{\\mathrm\{attack\}\}\}\{\\mathrm\{Acc\}\_\{\\mathrm\{clean\}\}\-\\mathrm\{Acc\}\_\{\\mathrm\{attack\}\}\}\.Here,Accclean\\mathrm\{Acc\}\_\{\\mathrm\{clean\}\}is the accuracy obtained by the clean summary, andAccattack\\mathrm\{Acc\}\_\{\\mathrm\{attack\}\}is the accuracy obtained by the attacked summary\. Thus,Recovery=0\\mathrm\{Recovery\}=0corresponds to the attacked summary, whileRecovery=1\\mathrm\{Recovery\}=1corresponds to full recovery to the clean\-summary accuracy\. A larger value of Recovery indicates stronger recovery of downstream task performance\.

#### \-D2Additional Empirical Results on multilinear extension summarization

##### Real\-data sensitivity on the multilinear\-extension summarization model

TABLE X:Real\-data sensitivity to the attack budgetϵ\\epsilonon the multilinear\-extension summarization model\. We useI=10I=10,n=50n=50,k=5k=5,λ=1\\lambda=1,Kattack=30K\_\{\\rm attack\}=30, andTattack=20T\_\{\\rm attack\}=20\. Random perturbation is averaged over 20 independent trials\.Normϵ\\boldsymbol\{\\epsilon\}MethodAvg\. Deg\.↑\\uparrowSucc\.↑\\uparrowInt\.↑\\uparrowℓ1\\ell\_\{1\}0\.1Proposed attack\-0\.01580\.20\-0\.000417PGD\-0\.07060\.20\-0\.001864Rand\.\-0\.03430\.00\-0\.0009071Proposed attack0\.01620\.700\.000428PGD0\.00840\.700\.000221Rand\.\-0\.03330\.00\-0\.0008812Proposed attack0\.03290\.600\.000869PGD0\.00970\.700\.000255Rand\.\-0\.03550\.10\-0\.000938ℓ2\\ell\_\{2\}0\.1Proposed attack\-0\.03630\.10\-0\.000960PGD\-0\.03270\.00\-0\.000863Rand\.\-0\.03700\.20\-0\.0009781Proposed attack\-0\.06620\.30\-0\.001748PGD\-0\.03530\.30\-0\.000934Rand\.\-0\.05990\.40\-0\.0015822Proposed attack0\.05480\.700\.001448PGD0\.00010\.700\.000002Rand\.\-0\.01920\.40\-0\.0005085Proposed attack0\.05480\.700\.001448PGD0\.00010\.700\.000002Rand\.0\.14070\.700\.003716ℓ∞\\ell\_\{\\infty\}0\.02Proposed attack\-0\.07470\.00\-0\.001973PGD\-0\.03070\.10\-0\.000812Rand\.\-0\.05050\.40\-0\.0013330\.05Proposed attack\-0\.07280\.20\-0\.001923PGD\-0\.07990\.00\-0\.002110Rand\.\-0\.02920\.40\-0\.0007700\.08Proposed attack\-0\.06180\.40\-0\.001632PGD\-0\.05290\.20\-0\.001396Rand\.\-0\.00450\.60\-0\.0001190\.1Proposed attack\-0\.09720\.40\-0\.002567PGD\-0\.02840\.20\-0\.000750Rand\.0\.00930\.600\.000246

Table[X](https://arxiv.org/html/2606.11804#A0.T10)reports the sensitivity of real\-data attacks to the perturbation budgetϵ\\epsilonunder three norm constraints\. Under theℓ1\\ell\_\{1\}\-norm constraint, the proposed attack becomes effective whenϵ\\epsilonincreases from0\.10\.1to11, and achieves the largest average degradation and attack intensity atϵ=2\\epsilon=2\. Although PGD obtains comparable success ratios atϵ=1\\epsilon=1andϵ=2\\epsilon=2, its degradation magnitude and intensity are much smaller\. Random perturbation remains negative across all testedℓ1\\ell\_\{1\}budgets, indicating that arbitrary feasible perturbations do not reliably reduce the clean summarization utility\.

Under theℓ2\\ell\_\{2\}\-norm constraint, all methods are weak at small budgets, while the proposed attack becomes effective atϵ=2\\epsilon=2\. At the larger budgetϵ=5\\epsilon=5, random perturbation also produces positive degradation, suggesting that sufficiently large unstructured changes can disrupt the similarity model\. However, this effect is not stable in smaller\-budget regimes and does not provide a controlled multi\-target attack mechanism\.

Theℓ∞\\ell\_\{\\infty\}\-norm results show a different pattern\. Across the tested budgets, the proposed attack and PGD attacks do not yield consistently positive average degradation, and their attack intensities remain small or negative\. Random perturbation becomes positive only atϵ=0\.1\\epsilon=0\.1, but the magnitude is also small\. This suggests that coordinate\-wise bounded perturbations are less effective for the MovieLens similarity structure than theℓ1\\ell\_\{1\}\- andℓ2\\ell\_\{2\}\-budgeted attacks\. Therefore, we treat theℓ∞\\ell\_\{\\infty\}case as an additional sensitivity analysis rather than the main real\-data attack setting\.

Overall, the results indicate that the proposed structure\-aware attack is most meaningful in low\-to\-moderateℓ1\\ell\_\{1\}\- andℓ2\\ell\_\{2\}\-budget regimes, where optimized perturbations outperform arbitrary feasible perturbations in both degradation magnitude and attack intensity\.

##### Per\-model real\-data attack results

Table[XI](https://arxiv.org/html/2606.11804#A0.T11)reports the per\-model attack effects on the real\-data MovieLens instance under representativeℓ1\\ell\_\{1\}\- andℓ2\\ell\_\{2\}\-norm constraints\. The results show that the degradation is not uniformly distributed across all target models, which is expected in the multi\-target setting because each victim model has a different similarity structure\. Nevertheless, the proposed attack produces clear positive degradation on several individual models and achieves larger average degradation than the PGD baseline under both representative constraints\. In contrast, random perturbation often yields near\-zero or negative degradation, indicating that simply perturbing the similarity matrix does not reliably reduce the clean\-objective value\. These per\-model results therefore support the aggregate results in Table[II](https://arxiv.org/html/2606.11804#S6.T2): the observed degradation is primarily due to the structured attack optimization rather than arbitrary perturbations\.

A negative degradation means that the attacked solution obtains a slightly larger clean\-objective value than the clean reference on that individual model\. This can occur because the perturbation is shared across all target models and is optimized for the aggregate multi\-target objective rather than for each model independently\.

TABLE XI:Per\-model real\-data attack results under representative norm constraints\.FcleanF\_\{\\rm clean\}denotes the clean\-reference objective; each method column reports attacked objective / degradation\.NormModelFcleanF\_\{\\rm clean\}Proposed attackPGD baselineRandom perturbationℓ1\\ell\_\{1\}141\.862541\.5888 / 0\.273741\.8251 / 0\.037341\.8688 / \-0\.0064240\.825841\.2047 / \-0\.378841\.1852 / \-0\.359440\.8614 / \-0\.0356338\.782538\.7469 / 0\.035738\.7701 / 0\.012438\.7823 / 0\.0002437\.157737\.0388 / 0\.119037\.4117 / \-0\.254037\.2135 / \-0\.0557535\.001834\.9913 / 0\.010434\.9269 / 0\.074935\.0040 / \-0\.0023636\.951836\.6008 / 0\.350936\.6484 / 0\.303337\.1697 / \-0\.2179736\.292136\.3042 / \-0\.012036\.1945 / 0\.097636\.3252 / \-0\.0330839\.905540\.0042 / \-0\.098739\.6352 / 0\.270239\.9055 / 0\.0000936\.949336\.9793 / \-0\.030137\.0650 / \-0\.115836\.9580 / \-0\.00871034\.798334\.7394 / 0\.058934\.7684 / 0\.029834\.7938 / 0\.0045ℓ2\\ell\_\{2\}141\.862541\.5888 / 0\.273741\.8470 / 0\.015442\.1490 / \-0\.2865240\.825841\.2047 / \-0\.378841\.1852 / \-0\.359440\.9139 / \-0\.0880338\.782538\.7469 / 0\.035738\.7701 / 0\.012438\.8155 / \-0\.0330437\.157737\.0388 / 0\.118937\.4117 / \-0\.254037\.2220 / \-0\.0643535\.001834\.9913 / 0\.010434\.9269 / 0\.074934\.9039 / 0\.0978636\.970836\.6008 / 0\.370036\.6484 / 0\.322436\.9617 / 0\.0091736\.292136\.3042 / \-0\.012136\.1945 / 0\.097636\.3021 / \-0\.0100839\.905539\.8089 / 0\.096639\.6352 / 0\.270239\.6811 / 0\.2244936\.949336\.9743 / \-0\.025037\.1580 / \-0\.208737\.0678 / \-0\.11851034\.798334\.7394 / 0\.058934\.7684 / 0\.029834\.7216 / 0\.0767

##### Auxiliary Real\-Data Downstream Evaluation on MovieLens

We additionally conduct a lightweight downstream evaluation on the MovieLens real\-data setting\. This experiment is intended as an auxiliary sanity check rather than the main downstream evidence, since the downstream genre\-classification task is not directly optimized by the summarization objective\. For each method, we use the rounded top\-kksummary as the training set for a 1\-nearest\-neighbor genre classifier, and use the remaining movies in the same clean fold as held\-out test items\. The classifier assigns each test item the genre label of the most similar selected summary item under the clean similarity matrix\. We report classification accuracy, the accuracy drop relative to the clean summary, and class coverage of the selected summary\.

TABLE XII:Auxiliary real\-data downstream evaluation on MovieLens\. Each top\-kksummary is used as the training set for a 1\-NN genre classifier, and the remaining movies in the same clean fold are used as held\-out test items\.NormMethodAcc\.↑\\uparrow𝚫\\boldsymbol\{\\Delta\}Acc\.↓\\downarrowClass cov\.↑\\uparrowℓ1\\ell\_\{1\}Clean summary0\.4130\.0000\.373Proposed attack0\.418\-0\.0040\.388PGD baseline0\.4020\.0110\.388Random perturbation0\.4110\.0020\.368Proposed robust0\.3820\.0310\.373PGD robust baseline0\.3620\.0510\.415ℓ2\\ell\_\{2\}Clean summary0\.4130\.0000\.373Proposed attack0\.431\-0\.0180\.387PGD baseline0\.3870\.0270\.352Random perturbation0\.4120\.0010\.374Proposed robust0\.3870\.0270\.331PGD robust baseline0\.3980\.0160\.331

Table[XII](https://arxiv.org/html/2606.11804#A0.T12)shows that the MovieLens downstream results do not exhibit a consistent attack–defense recovery pattern\. Under theℓ1\\ell\_\{1\}\- andℓ2\\ell\_\{2\}\-norm settings, some attacked summaries achieve accuracy comparable to or slightly higher than the clean summary, while robust summaries do not consistently improve downstream accuracy\. This behavior suggests that the lightweight genre\-classification task is strongly affected by class coverage and label distribution in the selected top\-kkmovies, whereas the robust summarization objective is designed to preserve similarity\-based summarization utility under perturbations rather than directly optimize genre classification\. Therefore, we use this real\-data downstream experiment only as an auxiliary sanity check\. The controlled clustered benchmark in the main text provides a clearer downstream evaluation because its class structure is aligned with the representative\-cluster structure used in the summarization model\.

### \-EAdditional Empirical Results on the Direct Continuous\-Score Summarization Objective

In this section, we also report empirical results on the direct continuous\-score summarization objective used in earlier continuous summarization formulations\. This objective uses the term

∑μmaxν⁡xν​sμ,ν,\\sum\_\{\\mu\}\\max\_\{\\nu\}x\_\{\\nu\}s\_\{\\mu,\\nu\},which provides an intuitive soft\-importance interpretation but is not the primary model covered by the DR\-submodular theoretical guarantee\. We include these results only as supplementary empirical evidence that the proposed attack\-defense framework can be applied beyond the main theoretical model\.

We conduct experiments on CIFAR\-10\[[2](https://arxiv.org/html/2606.11804#bib.bib20)\], MNIST\[[10](https://arxiv.org/html/2606.11804#bib.bib11)\], and Fashion\-MNIST\[[27](https://arxiv.org/html/2606.11804#bib.bib12)\]\. Unless otherwise specified, the main numerical results are reported on CIFAR\-10, while MNIST and Fashion\-MNIST are used for additional visual validation\. In each experiment, we constructI=10I=10victim summarization models, and each model containsn=50n=50images sampled from the raw dataset\. Table[XIII](https://arxiv.org/html/2606.11804#A0.T13)summarizes the main mathematical notations used in the experiments\. Specifically, we consider three attack types, corresponding tol1l\_\{1\}\-,l2l\_\{2\}\-, andl∞l\_\{\\infty\}\-norm constraints\. Forp∈\{1,2\}p\\in\\\{1,2\\\}, the attack budget is chosen fromϵp∈\[0\.01,10\]\\epsilon\_\{p\}\\in\[0\.01,10\], and forp=∞p=\\infty, we useϵ∞∈\[0\.1,1\]\\epsilon\_\{\\infty\}\\in\[0\.1,1\]\. The feasible set of summarization solutions is𝒳∈\[0,D\]n\\mathcal\{X\}\\in\[0,D\]^\{n\}withD∈\{0\.1,1,10\}D\\in\\\{0\.1,1,10\\\}\. Additionally, i\) For the proposed attack algorithm, we initialize𝐯0=𝟎\\mathbf\{v\}\_\{0\}=\\mathbf\{0\}and𝐰0=1I​𝟏\\mathbf\{w\}\_\{0\}=\\frac\{1\}\{I\}\\mathbf\{1\}, and setKattack=100K\_\{\\rm attack\}=100andTattack=30T\_\{\\rm attack\}=30\. ii\) For the robust defense algorithm, we initialize𝐯0=𝟎\\mathbf\{v\}\_\{0\}=\\mathbf\{0\}and𝐰0=13​𝟏\\mathbf\{w\}\_\{0\}=\\frac\{1\}\{3\}\\mathbf\{1\}, since three attack types are considered, and useKrobust=100K\_\{\\rm robust\}=100,Trobust=30T\_\{\\rm robust\}=30, andγ=0\.1\\gamma=0\.1\.

TABLE XIII:Key experimental parameters and evaluation metrics\.Symbol / MetricMeaningϵp\\epsilon\_\{p\}Attack budget under theℓp\\ell\_\{p\}\-norm constraintKattackK\_\{\\rm attack\}Outer iterations of Alg\.[2](https://arxiv.org/html/2606.11804#alg2)TattackT\_\{\\rm attack\}Inner iterations ofℳgreedy\\mathcal\{M\}\_\{\\rm greedy\}in Alg\.[2](https://arxiv.org/html/2606.11804#alg2)KrobustK\_\{\\rm robust\}Outer iterations of Alg\.[3](https://arxiv.org/html/2606.11804#alg3)TrobustT\_\{\\rm robust\}Inner iterations of Alg\.[3](https://arxiv.org/html/2606.11804#alg3)Avg\. Deg\.Average degradation under attackSucc\. RatioFraction of victim models successfully degradedIntensityNormalized attack intensityLossRelative clean\-utility change under robust optimizationRobustnessRelative clean\-attacked variation of the robust solutionMitigationImprovement over attacked greedy under the clean objective

##### Attack Performance underlpl\_\{p\}\-Norm Constraints

We first compare the proposed attack generator with a representative gradient\-based baseline, and then study the effect of the attack budget and feasible\-set size on attack performance\.

Comparison with a Gradient\-Based Baseline\.The representative methods summarized in Table[I](https://arxiv.org/html/2606.11804#S2.T1)differ substantially in target setting and structural assumptions\. In particular, the methods in\[[1](https://arxiv.org/html/2606.11804#bib.bib45)\]do not explicitly address the continuous multi\-target setting considered here\. We therefore compare our method with a representative gradient\-based baseline for general non\-convex min\-max optimization\[[25](https://arxiv.org/html/2606.11804#bib.bib44)\], which is directly applicable to our attack setting\.

As shown in Table[XIV](https://arxiv.org/html/2606.11804#A0.T14), the proposed method consistently achieves larger average degradation and attack intensity across all three attack constraints\. Under thel1l\_\{1\}\-norm setting, it also attains a higher success ratio than the gradient\-based baseline\. Under thel2l\_\{2\}\- andl∞l\_\{\\infty\}\-norm settings, both methods achieve the same success ratio, while the proposed method still yields slightly stronger degradation and intensity\. These results show that the proposed attack generator is empirically competitive with, and in these representative settings slightly stronger than, the gradient\-based baseline\.

TABLE XIV:Comparison with the gradient\-based baseline under different attack constraints \(D=1,ϵ=1,1,0\.5D=1,\\epsilon=1,1,0\.5forl1,l2,l∞l\_\{1\},l\_\{2\},l\_\{\\infty\}\)\.MetricMethod𝒍𝟏\\boldsymbol\{l\_\{1\}\}𝒍𝟐\\boldsymbol\{l\_\{2\}\}𝒍∞\\boldsymbol\{l\_\{\\infty\}\}Success Ratio \(%\)↑\\uparrowProposed10010090Baseline9010090Avg\. Degradation↑\\uparrowProposed0\.95830\.99070\.8292Baseline0\.79330\.96440\.6948Attack Intensity \(%\)↑\\uparrowProposed6\.786\.935\.94Baseline5\.616\.754\.98

Effect of the Attack Budgetϵp\\epsilon\_\{p\}and Feasible\-Set SizeDDWe next evaluate how attack performance changes with the attack budget and the feasible\-set size\. Figure[4](https://arxiv.org/html/2606.11804#A0.F4)shows the average attack intensity under differentlpl\_\{p\}\-norm constraints\.

Overall, the attack intensity increases asϵp\\epsilon\_\{p\}becomes larger\. Moreover, the effect ofDDdepends on the attack type\. Underl1l\_\{1\}\- andl2l\_\{2\}\-norm constraints, the influence ofDDis relatively limited\. For example, whenϵp=10\\epsilon\_\{p\}=10, the average attack intensity lies in a narrow range under bothl1l\_\{1\}\- andl2l\_\{2\}\-norm constraints\. In contrast, under thel∞l\_\{\\infty\}\-norm constraint, the attack intensity is much more sensitive toDD\. For instance, whenϵ∞=1\.0\\epsilon\_\{\\infty\}=1\.0, the intensity grows substantially from the caseD=0\.1D=0\.1to the caseD=10D=10\. This suggests that the feasible\-set scale plays a more important role under coordinate\-wise bounded perturbations\.

Attack Success Ratio under Different Settings\.Besides the average attack intensity, we also report the success ratio of attacks in Table[XV](https://arxiv.org/html/2606.11804#A0.T15)\. The results show that the proposed attack achieves a high success probability across a wide range of parameter settings\. In particular, the success ratio approaches or reaches100%100\\%once the attack budget exceeds a moderate threshold\. For example, under thel2l\_\{2\}\-norm setting, all attacks succeed whenϵ2≥0\.05\\epsilon\_\{2\}\\geq 0\.05\.

TABLE XV:Attack success ratio of Alg\.[2](https://arxiv.org/html/2606.11804#alg2)underlpl\_\{p\}\-norm attacks \(p=1,2,∞p=1,2,\\infty\) across differentDD\(D=0\.1,1,10D=0\.1,1,10\) andϵ\\epsilonvalues\. Parameters:η\\etavalues from Tab\.[XVIII](https://arxiv.org/html/2606.11804#A0.T18)\.DDϵp​\(p=1,2\)\\epsilon\_\{p\}\(p=1,2\)0\.010\.050\.10\.51\.05\.010\.0Ratioatt​\(p=1,ϵ1,D\)\\textbf\{Ratio\}^\{\\text\{att\}\}\(p=1,\\epsilon\_\{1\},D\)underl1l\_\{1\}\-norm0\.10\.800\.700\.801\.001\.001\.001\.001\.00\.800\.800\.901\.001\.001\.001\.0010\.00\.800\.900\.801\.001\.001\.001\.00Ratioatt​\(p=2,ϵ2,D\)\\textbf\{Ratio\}^\{\\text\{att\}\}\(p=2,\\epsilon\_\{2\},D\)underl2l\_\{2\}\-norm0\.10\.601\.001\.001\.001\.001\.001\.001\.00\.901\.001\.001\.001\.001\.001\.0010\.00\.901\.001\.001\.001\.001\.001\.00

DDϵp​\(p=∞\)\\epsilon\_\{p\}\(p=\\infty\)0\.10\.20\.30\.40\.50\.60\.70\.80\.91\.0Ratioatt​\(p=∞,ϵ∞,D\)\\textbf\{Ratio\}^\{\\text\{att\}\}\(p=\\infty,\\epsilon\_\{\\infty\},D\)underl∞l\_\{\\infty\}\-norm0\.10\.900\.800\.800\.800\.800\.900\.900\.900\.900\.901\.00\.501\.001\.001\.001\.001\.001\.001\.001\.001\.0010\.01\.001\.001\.001\.001\.001\.001\.001\.001\.001\.00

![Refer to caption](https://arxiv.org/html/2606.11804v1/x1.png)\(a\)l1l\_\{1\}\-norm
![Refer to caption](https://arxiv.org/html/2606.11804v1/x2.png)\(b\)l2l\_\{2\}\-norm
![Refer to caption](https://arxiv.org/html/2606.11804v1/x3.png)\(c\)l∞l\_\{\\infty\}\-norm

Figure 4:Average attack intensity underlpl\_\{p\}\-norm constraints of Alg\.[2](https://arxiv.org/html/2606.11804#alg2)\. ParametersKattack=100,Tattack=30K\_\{\\rm attack\}=100,T\_\{\\rm attack\}=30in Alg\.[1](https://arxiv.org/html/2606.11804#alg1)andη\\etarefers to Tab\.[XVIII](https://arxiv.org/html/2606.11804#A0.T18)\. “Dots” represents average attack intensity \(Intensityatt​\(p,ϵp,D\)\\textbf\{Intensity\}^\{\\rm att\}\(p,\\epsilon\_\{p\},D\)\) of Alg\.[2](https://arxiv.org/html/2606.11804#alg2)underlpl\_\{p\}\-norm \(p=1,2,∞p=1,2,\\infty\) constraints\. “Lines” illustrate trends of attack intensity increasing withϵp\\epsilon\_\{p\}and “YY\-axis” represents average function differences \(Δ¯att​\(p,ϵp,D\)\\bar\{\\Delta\}^\{\\rm att\}\(p,\\epsilon\_\{p\},D\)\)\)\.
##### Robustness of the Defense Algorithm under Mixed Attacks

We now evaluate the proposed defense algorithm under mixed attack types\. In particular, we focus on three questions: 1\) how the regularization parameterγ\\gammaaffects the trade\-off between clean\-data utility and robustness; 2\) how the proposed robust algorithm compares with a representative gradient\-based robust baseline; and 3\) whether the proposed robust algorithm can effectively mitigate the impact of attacks\.

Utility–Robustness Trade\-off under Differentγ\\gamma\.The proposed defense algorithm optimizes Eq\.[4](https://arxiv.org/html/2606.11804#S3.E4), where the regularization parameterγ\\gammacontrols the balance between clean\-data utility and robustness\. As shown in Table[XVI](https://arxiv.org/html/2606.11804#A0.T16), larger values ofγ\\gammagenerally lead to stronger robustness\. For example, under thel∞l\_\{\\infty\}\-norm attack, the robustness value decreases from0\.840\.84whenγ=0\.1\\gamma=0\.1to0\.220\.22whenγ=10\\gamma=10, and under thel2l\_\{2\}\-norm attack it decreases from0\.430\.43to0\.270\.27\. Moreover, for a fixedγ\\gamma, the robustness gap across different attack types becomes smaller whenγ\\gammais larger, suggesting that the defense becomes more balanced against mixed attacks\.

TABLE XVI:Performance metrics of Alg\.[3](https://arxiv.org/html/2606.11804#alg3)under differentγ\\gammavalues\(Krobust=100,Trobust=30,D=1,ϵ=1,1,0\.5\(K\_\{\\rm robust\}=100,T\_\{\\rm robust\}=30,D=1,\\epsilon=1,1,0\.5forl1,l2,l∞l\_\{1\},l\_\{2\},l\_\{\\infty\}\)\.MetricsDifferentγ\\gammavaluesγ=0\.1\\gamma=0\.1γ=1\\gamma=1γ=10\\gamma=10Loss \(%\)↓\\downarrow2\.962\.944\.01Robustness \(%\)↓\\downarrowl∞l\_\{\\infty\}0\.840\.810\.22l1l\_\{1\}0\.880\.870\.34l2l\_\{2\}0\.430\.450\.27Mitigation \(%\)↑\\uparrowl∞l\_\{\\infty\}5\.825\.865\.52l1l\_\{1\}4\.344\.363\.89l2l\_\{2\}3\.863\.883\.22

This behavior is consistent with the role of the regularization term: a largerγ\\gammaencourages the weight vector𝐰\\mathbf\{w\}to remain more balanced across attack types, thereby reducing the dominance of any single attack type and improving stability under perturbed inputs\. However, Table[XVI](https://arxiv.org/html/2606.11804#A0.T16)also shows that excessively largeγ\\gammamay increase the clean\-data loss\. Therefore,γ\\gammainduces a clear utility–robustness trade\-off, andγ=1\\gamma=1provides a good balance in our experiments\.

Comparison with a Gradient\-Based Robust Baseline\.The representative methods summarized in Table[I](https://arxiv.org/html/2606.11804#S2.T1)differ substantially in model assumptions and attack settings\. In particular, existing robust DR\-submodular methods such as\[[11](https://arxiv.org/html/2606.11804#bib.bib8),[13](https://arxiv.org/html/2606.11804#bib.bib7)\]mainly focus on monotone settings and do not explicitly address mixed attacks\. We therefore compare our method with a representative gradient\-based robust baseline that is directly compatible with the mixed\-attack setting considered here\.

As shown in Table[XVII](https://arxiv.org/html/2606.11804#A0.T17), the proposed robust algorithm consistently achieves near\-zero or much smaller clean\-data loss and substantially smaller robustness values than the gradient\-based baseline, while maintaining positive mitigation across all three attack constraints\. In contrast, the gradient\-based baseline suffers from much larger clean\-data loss and negative mitigation in all three representative settings, indicating that it fails to consistently offset the attack effect\. These results support the advantage of structure\-aware robust optimization for continuous data summarization\.

TABLE XVII:Comparison with the gradient\-based robust baseline under different attack constraints \(D=1,γ=1,ϵ=1,1,0\.5D=1,\\gamma=1,\\epsilon=1,1,0\.5forl1,l2,l∞l\_\{1\},l\_\{2\},l\_\{\\infty\}\)\.MetricMethod𝒍𝟏\\boldsymbol\{l\_\{1\}\}𝒍𝟐\\boldsymbol\{l\_\{2\}\}𝒍∞\\boldsymbol\{l\_\{\\infty\}\}Loss \(%\)↓\\downarrowProposed\-0\.2250\.8111\.588Baseline30\.6631\.5329\.58Robustness \(%\)↓\\downarrowProposed0\.6640\.4010\.649Baseline32\.3329\.1937\.01Mitigation \(%\)↑\\uparrowProposed6\.2996\.6416\.747Baseline\-47\.53\-45\.40\-50\.95

Defense Effectiveness and Mitigation\.We next examine whether the proposed defense can effectively reduce the impact of attacks\. From Table[XVI](https://arxiv.org/html/2606.11804#A0.T16), all mitigation values are positive for all tested choices ofγ\\gammaand all three attack types\. This indicates that the proposed robust algorithm consistently alleviates the degradation caused by attacks\.

Moreover, the mitigation results should be interpreted together with the loss values\. Although the defense algorithm introduces a small utility loss under clean data, the reduction in attack impact is consistently larger, showing that the robust formulation is beneficial overall\. For example, whenγ=1\\gamma=1, the defense achieves positive mitigation under all three norm\-constrained attacks while maintaining relatively small clean\-data loss\. These results demonstrate that the proposed defense algorithm can effectively improve robustness against mixed attacks in continuous data summarization\.

##### Visualization Results on Multiple Datasets

We further provide qualitative visualization results for the attack algorithm \(Alg\.[2](https://arxiv.org/html/2606.11804#alg2)\), the plain greedy summarization algorithm \(Alg\.[1](https://arxiv.org/html/2606.11804#alg1)\), and the proposed robust defense algorithm \(Alg\.[3](https://arxiv.org/html/2606.11804#alg3)\) on CIFAR\-10, MNIST, and Fashion\-MNIST\. To generate the displayed summaries, we first normalize the continuous solution𝐱\\mathbf\{x\}into\[0,1\]\[0,1\], then convert it into a discrete selection vector using a threshold, and finally select images according to the resulting discrete solution\.

Figures[5](https://arxiv.org/html/2606.11804#A0.F5)–[7](https://arxiv.org/html/2606.11804#A0.F7)show that the attacked outputs differ substantially from the plain greedy outputs, while the robust outputs recover a noticeably larger portion of the original selection patterns\. For instance, in Fig\.[5](https://arxiv.org/html/2606.11804#A0.F5), only two selected images remain unchanged after attack, whereas the robust output recovers eleven images that coincide with the plain greedy output\. Similar phenomena are observed on CIFAR\-10 and Fashion\-MNIST, consistent with the numerical results\.

Alg\.[2](https://arxiv.org/html/2606.11804#alg2)outputs![Refer to caption](https://arxiv.org/html/2606.11804v1/figs/mnist_att.png)Alg\.[1](https://arxiv.org/html/2606.11804#alg1)outputs![Refer to caption](https://arxiv.org/html/2606.11804v1/figs/mnist_pla.png)Alg\.[3](https://arxiv.org/html/2606.11804#alg3)outputs![Refer to caption](https://arxiv.org/html/2606.11804v1/figs/mnist_rob.png)

Figure 5:Visualization results of Alg\.[2](https://arxiv.org/html/2606.11804#alg2)\(attack algorithm\), Alg\.[1](https://arxiv.org/html/2606.11804#alg1)\(plain submodular algorithm\), and Alg\.[3](https://arxiv.org/html/2606.11804#alg3)\(robust algorithm under attack\) outputs underl1l\_\{1\}\-norm attack for dataset MNIST \(D=1D=1,ϵ=1\\epsilon=1, threshold=0\.6=0\.6\)\.Alg\. 2 outputs![Refer to caption](https://arxiv.org/html/2606.11804v1/figs/cifar10_att.png)Alg\. 1 outputs![Refer to caption](https://arxiv.org/html/2606.11804v1/figs/cifar10_ori.png)Alg\. 3 outputs![Refer to caption](https://arxiv.org/html/2606.11804v1/figs/cifar10_rob.png)

Figure 6:Visualization results of attacked \(Alg\.[2](https://arxiv.org/html/2606.11804#alg2)\), plain \(Alg\.[1](https://arxiv.org/html/2606.11804#alg1)without attack\) and robust \(Alg\.[3](https://arxiv.org/html/2606.11804#alg3)with attack\) outputs underl1l\_\{1\}\-norm attack for dataset CIFAR\-10 \(D=1D=1,ϵ=1\\epsilon=1and threshold=0\.493\)\.Alg\. 2 outputs![Refer to caption](https://arxiv.org/html/2606.11804v1/figs/fashio_att.png)Alg\. 1 outputs![Refer to caption](https://arxiv.org/html/2606.11804v1/figs/fashion_ori.png)Alg\. 3 outputs![Refer to caption](https://arxiv.org/html/2606.11804v1/figs/fashion_rob.png)

Figure 7:Visualization results of attacked \(Alg\.[2](https://arxiv.org/html/2606.11804#alg2)\), plain \(Alg\.[1](https://arxiv.org/html/2606.11804#alg1)without attack\) and robust \(Alg\.[3](https://arxiv.org/html/2606.11804#alg3)with attack\) outputs underl1l\_\{1\}\-norm attacks for dataset Fashion MNIST \(D=1D=1,ϵ=1\\epsilon=1and threshold=0\.48\)\.
##### Additional Results for the Attack Algorithm \(Alg\.[2](https://arxiv.org/html/2606.11804#alg2)\)

This section provides additional results on the convergence behavior of Alg\.[2](https://arxiv.org/html/2606.11804#alg2)and the per\-model attack effects under different attack budgets\.

Convergence of the Attack Algorithm\.Fig\.[8](https://arxiv.org/html/2606.11804#A0.F8)illustrates the effect of the step sizeη\\etaon the convergence of Alg\.[2](https://arxiv.org/html/2606.11804#alg2)under different attack types\. WhenD=1D=1, choosingη\\etain the range\[0\.05,0\.15\]\[0\.05,0\.15\]yields stable convergence for all three norm\-constrained attacks\. In contrast, excessively small step sizes \(e\.g\.,η=0\.005\\eta=0\.005for thel1l\_\{1\}\-norm attack,η=0\.0001\\eta=0\.0001for thel2l\_\{2\}\-norm attack, andη=0\.001\\eta=0\.001for thel∞l\_\{\\infty\}\-norm attack\) lead to non\-convergence or convergence to worse solutions\. This indicates that Alg\.[2](https://arxiv.org/html/2606.11804#alg2)is relatively insensitive to moderate changes inη\\eta, but overly small step sizes can significantly degrade convergence and solution quality\.

Tab\.[XVIII](https://arxiv.org/html/2606.11804#A0.T18)lists theη\\etavalues used for thel1l\_\{1\}\- andl2l\_\{2\}\-norm attacks under different\(D,ϵ\)\(D,\\epsilon\)settings\. These values are chosen so that the norm of the generated perturbation𝐯\\mathbf\{v\}approaches the prescribed budgetϵ\\epsilonas closely as possible\. For thel∞l\_\{\\infty\}\-norm attack, we use the theoretically motivated choiceη=1/Kattack\\eta=1/\\sqrt\{K\_\{\\rm attack\}\}withKattack=100K\_\{\\rm attack\}=100, following Theorem[2](https://arxiv.org/html/2606.11804#Thmtheorem2)\. In this case, whether each coordinate of𝐯\\mathbf\{v\}reachesϵ\\epsilonis not itself a meaningful indicator of attack strength\.

TABLE XVIII:Values ofη\\etain Alg\.[2](https://arxiv.org/html/2606.11804#alg2)underl1/l2l\_\{1\}/l\_\{2\}\-norm attacks with varying\(D,ϵ\)\(D,\\epsilon\)configurations\.DDη\\etafor differentϵ\\epsilonvalues0\.010\.050\.100\.501\.005\.0010\.000\.10\.05000\.30000\.80001\.00001\.000010\.000020\.00001\.00\.00500\.04000\.05000\.05000\.10000\.50002\.000010\.00\.00010\.00040\.00080\.00300\.00700\.05000\.1000

![Refer to caption](https://arxiv.org/html/2606.11804v1/x4.png)\(a\)l1l\_\{1\}\-norm
![Refer to caption](https://arxiv.org/html/2606.11804v1/x5.png)\(b\)l2l\_\{2\}\-norm
![Refer to caption](https://arxiv.org/html/2606.11804v1/x6.png)\(c\)l∞l\_\{\\infty\}\-norm

Figure 8:Convergence behavior of Alg\.[2](https://arxiv.org/html/2606.11804#alg2)underlpl\_\{p\}\-norm attacks\(p=1,2,∞\)\(p=1,2,\\infty\)with varyingη\\etavalues\. Parameters:Kattack=100K\_\{\\rm attack\}=100,Tattack=30T\_\{\\rm attack\}=30, andD=1D=1\.Per\-model Attack Effects under Different Attack Budgets\.For a fixedDD, withKattack=100K\_\{\\rm attack\}=100andTattack=30T\_\{\\rm attack\}=30in Alg\.[2](https://arxiv.org/html/2606.11804#alg2), the objective value generally decreases as the attack budget increases\. In particular, all models are successfully attacked whenϵ1≥0\.5\\epsilon\_\{1\}\\geq 0\.5in Tabs\.[XIX](https://arxiv.org/html/2606.11804#A0.T19)–[XXI](https://arxiv.org/html/2606.11804#A0.T21), and whenϵ2≥0\.05\\epsilon\_\{2\}\\geq 0\.05in Tabs\.[XXII](https://arxiv.org/html/2606.11804#A0.T22)–[XXIV](https://arxiv.org/html/2606.11804#A0.T24), for allD∈\{0\.1,1,10\}D\\in\\\{0\.1,1,10\\\}\. For thel∞l\_\{\\infty\}\-norm attack, the per\-model results are more sensitive to the value ofDD\. For example, Model 7 is never successfully attacked whenD=0\.1D=0\.1, as shown in Tab\.[XXV](https://arxiv.org/html/2606.11804#A0.T25)\. In contrast, whenD=10D=10, all models can be successfully attacked, as shown in Tab\.[XXVII](https://arxiv.org/html/2606.11804#A0.T27)\. These results are consistent with the averaged trends reported in the main text and further illustrate how the feasible\-set scale affects the strength of thel∞l\_\{\\infty\}\-norm attack\.

TABLE XIX:Objective valueFFof Alg\.[1](https://arxiv.org/html/2606.11804#alg1)underl1l\_\{1\}\-norm attacks with varyingϵ1∈\[0,10\]\\epsilon\_\{1\}\\in\[0,10\]\. Parameters:D=0\.1D=0\.1, andη\\etavalues from Tab\.[XVIII](https://arxiv.org/html/2606.11804#A0.T18)\.ϵ𝟏\\epsilon\_\{1\}Model1\{\\rm Model\}\_\{1\}Model2\{\\rm Model\}\_\{2\}Model3\{\\rm Model\}\_\{3\}Model4\{\\rm Model\}\_\{4\}Model5\{\\rm Model\}\_\{5\}Model6\{\\rm Model\}\_\{6\}Model7\{\\rm Model\}\_\{7\}Model8\{\\rm Model\}\_\{8\}Model9\{\\rm Model\}\_\{9\}Model10\{\\rm Model\}\_\{10\}0\.000\.15110\.14610\.14690\.14290\.14360\.14910\.14340\.14790\.14840\.14840\.010\.14930\.14520\.14540\.14510\.14300\.14820\.14690\.14780\.14700\.14730\.050\.15000\.14540\.14540\.14580\.14370\.14350\.14650\.14640\.14740\.14290\.100\.14980\.14500\.14200\.14520\.13860\.14790\.14600\.14720\.14220\.14200\.500\.13730\.13340\.13140\.13270\.13200\.13280\.13430\.13680\.13550\.13591\.000\.13650\.13190\.13520\.13590\.12960\.13260\.13240\.13510\.13680\.13345\.000\.13420\.13080\.13170\.13160\.12940\.13150\.13260\.13500\.13330\.135010\.000\.13360\.13030\.13100\.13140\.13080\.13460\.13040\.13440\.13280\.1335

TABLE XX:Objective valuesFFof Alg\.[1](https://arxiv.org/html/2606.11804#alg1)underl1l\_\{1\}\-norm attacks with varyingϵ1∈\[0,10\]\\epsilon\_\{1\}\\in\[0,10\]\. Parameters:D=1D=1,η\\etavalues from Tab\.[XVIII](https://arxiv.org/html/2606.11804#A0.T18)\.ϵ𝟏\\epsilon\_\{1\}Model1\{\\rm Model\}\_\{1\}Model2\{\\rm Model\}\_\{2\}Model3\{\\rm Model\}\_\{3\}Model4\{\\rm Model\}\_\{4\}Model5\{\\rm Model\}\_\{5\}Model6\{\\rm Model\}\_\{6\}Model7\{\\rm Model\}\_\{7\}Model8\{\\rm Model\}\_\{8\}Model9\{\\rm Model\}\_\{9\}Model10\{\\rm Model\}\_\{10\}0\.0014\.775714\.299614\.382013\.950214\.059214\.592513\.949014\.468614\.520914\.51940\.0114\.720113\.840214\.333214\.345113\.614614\.527014\.392313\.903914\.422414\.41540\.0514\.461214\.201514\.149014\.232613\.919314\.112314\.208714\.163513\.785813\.77070\.1014\.228813\.734614\.267213\.748713\.531914\.048013\.959713\.883213\.818114\.28580\.5013\.632213\.001813\.187613\.121912\.833113\.085013\.227813\.203813\.329713\.16091\.0013\.169212\.883012\.800313\.051112\.722013\.163613\.093113\.224412\.859113\.16855\.0013\.155312\.836113\.088612\.800612\.733712\.986512\.836713\.029712\.703513\.076810\.0012\.957012\.943812\.895913\.149612\.876612\.944712\.727413\.219912\.890013\.0697

TABLE XXI:Objective valuesFFof Alg\.[1](https://arxiv.org/html/2606.11804#alg1)underl1l\_\{1\}\-norm attacks with varyingϵ1∈\[0,10\]\\epsilon\_\{1\}\\in\[0,10\]\. Parameters:D=10D=10,η\\etavalues from Tab\.[XVIII](https://arxiv.org/html/2606.11804#A0.T18)\.ϵ𝟏\\epsilon\_\{1\}Model1\{\\rm Model\}\_\{1\}Model2\{\\rm Model\}\_\{2\}Model3\{\\rm Model\}\_\{3\}Model4\{\\rm Model\}\_\{4\}Model5\{\\rm Model\}\_\{5\}Model6\{\\rm Model\}\_\{6\}Model7\{\\rm Model\}\_\{7\}Model8\{\\rm Model\}\_\{8\}Model9\{\\rm Model\}\_\{9\}Model10\{\\rm Model\}\_\{10\}0\.001474\.23241426\.84921435\.00231391\.85541402\.89591410\.43951391\.69931443\.64831448\.88611448\.71910\.011462\.90981416\.60631422\.48031376\.00691398\.60401442\.14291415\.49351425\.02801424\.23311433\.62940\.051449\.60081407\.99321423\.41871383\.41851345\.35091443\.23301375\.91751383\.72701373\.54481433\.16480\.101416\.39751364\.59701371\.78841375\.61481353\.92481439\.15161418\.79151418\.28761373\.60331428\.76770\.501344\.70701302\.47601289\.90801302\.35891269\.60111302\.74271305\.09361330\.55931257\.78891321\.04851\.001320\.77591308\.10581287\.87531299\.58531284\.22001299\.09181289\.33301340\.88831308\.67521324\.15195\.001286\.73901272\.44381285\.63461283\.53201285\.09121273\.18991296\.51361306\.50481271\.80131296\.255610\.001306\.18741281\.96261285\.02191288\.27211274\.91801282\.16301281\.89911300\.27691285\.94481311\.3829

TABLE XXII:Objective valuesFFof Alg\.[1](https://arxiv.org/html/2606.11804#alg1)underl2l\_\{2\}\-norm attacks with varyingϵ2∈\[0,10\]\\epsilon\_\{2\}\\in\[0,10\]\. Parameters:D=0\.1D=0\.1,η\\etavalues from Tab\.[XVIII](https://arxiv.org/html/2606.11804#A0.T18)\.ϵ𝟐\\epsilon\_\{2\}Model1\{\\rm Model\}\_\{1\}Model2\{\\rm Model\}\_\{2\}Model3\{\\rm Model\}\_\{3\}Model4\{\\rm Model\}\_\{4\}Model5\{\\rm Model\}\_\{5\}Model6\{\\rm Model\}\_\{6\}Model7\{\\rm Model\}\_\{7\}Model8\{\\rm Model\}\_\{8\}Model9\{\\rm Model\}\_\{9\}Model10\{\\rm Model\}\_\{10\}0\.000\.15110\.14610\.14690\.14290\.14360\.14910\.14340\.14790\.14840\.14840\.010\.14560\.14530\.14210\.14650\.14360\.14840\.14350\.14790\.14790\.14770\.050\.14790\.14440\.14020\.14130\.13850\.14130\.14020\.14640\.14640\.14710\.100\.14820\.14370\.14300\.14030\.13700\.14250\.13970\.14330\.13870\.14450\.500\.14550\.13630\.13680\.13620\.13400\.14060\.13550\.13690\.13850\.14171\.000\.14720\.13590\.13830\.13430\.13580\.13920\.13600\.13640\.13690\.14225\.000\.13530\.13210\.13450\.13340\.13100\.13340\.13440\.13660\.13220\.134510\.000\.13410\.13130\.13200\.13260\.13290\.13430\.13040\.13500\.13060\.1337

TABLE XXIII:Objective valuesFFof Alg\.[1](https://arxiv.org/html/2606.11804#alg1)underl2l\_\{2\}\-norm attacks with varyingϵ2∈\[0,10\]\\epsilon\_\{2\}\\in\[0,10\]\. Parameters:D=1D=1,η\\etavalues from Tab\.[XVIII](https://arxiv.org/html/2606.11804#A0.T18)\.ϵ𝟐\\epsilon\_\{2\}Model1\{\\rm Model\}\_\{1\}Model2\{\\rm Model\}\_\{2\}Model3\{\\rm Model\}\_\{3\}Model4\{\\rm Model\}\_\{4\}Model5\{\\rm Model\}\_\{5\}Model6\{\\rm Model\}\_\{6\}Model7\{\\rm Model\}\_\{7\}Model8\{\\rm Model\}\_\{8\}Model9\{\\rm Model\}\_\{9\}Model10\{\\rm Model\}\_\{10\}0\.0014\.775714\.299614\.382013\.950214\.059214\.592513\.949014\.468614\.520914\.51940\.0114\.360914\.032613\.589714\.013413\.476813\.585313\.754514\.158314\.372914\.04570\.0513\.367413\.800213\.143013\.298513\.027013\.471513\.619413\.890113\.684713\.83870\.113\.855013\.326313\.450913\.288513\.414313\.304313\.356814\.122413\.453413\.43390\.513\.227413\.329213\.316713\.282213\.096813\.360813\.376713\.420413\.375813\.29691\.013\.602913\.384013\.889813\.679413\.252113\.595013\.255613\.548413\.115313\.41895\.013\.116612\.947213\.096812\.929712\.896213\.189412\.901913\.136612\.982313\.176410\.012\.990013\.109712\.961312\.814212\.717413\.027612\.828913\.163713\.012813\.0594

TABLE XXIV:Objective valuesFFof Alg\.[1](https://arxiv.org/html/2606.11804#alg1)underl2l\_\{2\}\-norm attacks with varyingϵ2∈\[0,10\]\\epsilon\_\{2\}\\in\[0,10\]\. Parameters:D=10D=10,η\\etavalues from Tab\.[XVIII](https://arxiv.org/html/2606.11804#A0.T18)\.ϵ𝟐\\epsilon\_\{2\}Model1\{\\rm Model\}\_\{1\}Model2\{\\rm Model\}\_\{2\}Model3\{\\rm Model\}\_\{3\}Model4\{\\rm Model\}\_\{4\}Model5\{\\rm Model\}\_\{5\}Model6\{\\rm Model\}\_\{6\}Model7\{\\rm Model\}\_\{7\}Model8\{\\rm Model\}\_\{8\}Model9\{\\rm Model\}\_\{9\}Model10\{\\rm Model\}\_\{10\}0\.001474\.23241426\.84921435\.00231391\.85541402\.89591410\.43951391\.69931443\.64831448\.88611448\.71910\.011393\.35621360\.06381374\.82731364\.26671322\.62391414\.87181324\.41191370\.10801370\.73631378\.84430\.051383\.63211383\.49091330\.06051307\.59151314\.52491349\.56081320\.02151362\.26231339\.11321404\.04970\.101410\.69061314\.62691332\.87001377\.22071345\.07311363\.33261340\.20591419\.61031345\.43991403\.31970\.501350\.55151332\.42071305\.35931304\.01241300\.35751336\.11501331\.54841346\.67611348\.26391329\.53031\.001363\.81971366\.52861338\.75421331\.98351367\.62431336\.47741305\.57361395\.54311336\.75581380\.13955\.001302\.34811292\.58271293\.32641294\.23221302\.14821298\.10311268\.58761322\.82871303\.68701323\.077810\.001328\.78721275\.88411304\.64431283\.50581298\.70701306\.29901276\.38631310\.07921272\.11411322\.5080

TABLE XXV:Objective valuesFFof Alg\.[1](https://arxiv.org/html/2606.11804#alg1)underl∞l\_\{\\infty\}\-norm attacks with varyingϵ∞∈\[0,1\]\\epsilon\_\{\\infty\}\\in\[0,1\]\. Parameters:D=0\.1D=0\.1,η=0\.1\\eta=0\.1\.ϵ∞\\epsilon\_\{\\infty\}Model1\{\\rm Model\}\_\{1\}Model2\{\\rm Model\}\_\{2\}Model3\{\\rm Model\}\_\{3\}Model4\{\\rm Model\}\_\{4\}Model5\{\\rm Model\}\_\{5\}Model6\{\\rm Model\}\_\{6\}Model7\{\\rm Model\}\_\{7\}Model8\{\\rm Model\}\_\{8\}Model9\{\\rm Model\}\_\{9\}Model10\{\\rm Model\}\_\{10\}0\.000\.15110\.14610\.14690\.14290\.14360\.14910\.14340\.14790\.14840\.14840\.100\.14790\.14490\.14030\.14110\.13800\.14660\.14580\.14650\.14760\.14720\.200\.14820\.14550\.14500\.14620\.13870\.14820\.14470\.14740\.14730\.14750\.300\.14820\.14550\.14500\.14620\.13870\.14820\.14470\.14740\.14730\.14750\.400\.14820\.14550\.14500\.14620\.13870\.14820\.14470\.14740\.14730\.14750\.500\.14820\.14550\.14500\.14620\.13870\.14820\.14470\.14740\.14730\.14750\.600\.14790\.14490\.14030\.14110\.13800\.14660\.14580\.14650\.14760\.14720\.700\.14790\.14490\.14030\.14110\.13800\.14660\.14580\.14650\.14760\.14720\.800\.14790\.14490\.14030\.14110\.13800\.14660\.14580\.14650\.14760\.14720\.900\.14790\.14490\.14030\.14110\.13800\.14660\.14580\.14650\.14760\.14721\.000\.14790\.14490\.14030\.14110\.13800\.14660\.14580\.14650\.14760\.1472

TABLE XXVI:Objective valuesFFof Alg\.[1](https://arxiv.org/html/2606.11804#alg1)underl∞l\_\{\\infty\}\-norm attacks with varyingϵ∞∈\[0,1\]\\epsilon\_\{\\infty\}\\in\[0,1\]\. Parameters:D=1D=1,η=0\.1\\eta=0\.1\.ϵ∞\\epsilon\_\{\\infty\}Model1\{\\rm Model\}\_\{1\}Model2\{\\rm Model\}\_\{2\}Model3\{\\rm Model\}\_\{3\}Model4\{\\rm Model\}\_\{4\}Model5\{\\rm Model\}\_\{5\}Model6\{\\rm Model\}\_\{6\}Model7\{\\rm Model\}\_\{7\}Model8\{\\rm Model\}\_\{8\}Model9\{\\rm Model\}\_\{9\}Model10\{\\rm Model\}\_\{10\}0\.0014\.775714\.299614\.382013\.950214\.059214\.592513\.949014\.468614\.520914\.51940\.1014\.720013\.837313\.826914\.332013\.617814\.606613\.950814\.472514\.520914\.48690\.2014\.755713\.560913\.663113\.587913\.579613\.930813\.706914\.006713\.934713\.87780\.3014\.744113\.592613\.503613\.435612\.746413\.509913\.483613\.701213\.057714\.29770\.4013\.273313\.026613\.066313\.245512\.955913\.453113\.755713\.186413\.564814\.16770\.5013\.159612\.921712\.815812\.877812\.895512\.875313\.053413\.027212\.650613\.21230\.6013\.116212\.949013\.045212\.806212\.823813\.034312\.872613\.117612\.889313\.20460\.7013\.089112\.949013\.025212\.806212\.786913\.034312\.854113\.107412\.967613\.09810\.8013\.089112\.949013\.025212\.806212\.786913\.034312\.854113\.107412\.967613\.09810\.9013\.089112\.949013\.025212\.806212\.786913\.034312\.854113\.107412\.967613\.09811\.0013\.089112\.949013\.025212\.806212\.786913\.034312\.854113\.107412\.967613\.0981

TABLE XXVII:Objective valuesFFof Alg\.[1](https://arxiv.org/html/2606.11804#alg1)underl∞l\_\{\\infty\}\-norm attacks with varyingϵ∞∈\[0,1\]\\epsilon\_\{\\infty\}\\in\[0,1\]\. Parameters:D=10D=10,η=0\.1\\eta=0\.1\.ϵ∞\\epsilon\_\{\\infty\}Model1\{\\rm Model\}\_\{1\}Model2\{\\rm Model\}\_\{2\}Model3\{\\rm Model\}\_\{3\}Model4\{\\rm Model\}\_\{4\}Model5\{\\rm Model\}\_\{5\}Model6\{\\rm Model\}\_\{6\}Model7\{\\rm Model\}\_\{7\}Model8\{\\rm Model\}\_\{8\}Model9\{\\rm Model\}\_\{9\}Model10\{\\rm Model\}\_\{10\}0\.001474\.23241426\.84921435\.00231391\.85541402\.89591410\.43951391\.69931443\.64831448\.88611448\.71910\.101356\.19321367\.82651336\.55551332\.45401348\.53021371\.40581336\.86401394\.62371379\.72311380\.92540\.201299\.14021318\.09101281\.04211293\.93221290\.96501298\.24201298\.53911316\.14461321\.34821314\.87290\.301330\.09281236\.72111291\.22221252\.34891297\.17341259\.01891276\.54071312\.25211313\.27991331\.80450\.401241\.20521302\.39151282\.05951273\.93691163\.98251110\.12211219\.54491310\.22181317\.00131246\.77360\.501323\.71561289\.55501255\.36761283\.36411236\.20721288\.73491293\.38221322\.78921210\.64881302\.77110\.601315\.13281290\.68971221\.07781312\.19901299\.51891169\.97331250\.76731262\.18561305\.93381309\.60770\.701302\.27651311\.21951295\.36731299\.97771312\.27511306\.19881301\.03841306\.32421302\.11751273\.00840\.801345\.03861235\.48231293\.44131308\.12461229\.80061243\.80611229\.25081237\.67801237\.82331329\.40450\.901303\.79231294\.70921283\.00931184\.02121300\.74841302\.79431283\.71631302\.20641313\.11541332\.18121\.001323\.49221234\.02111288\.25011247\.88891237\.52961282\.05591163\.02161313\.15261225\.37471321\.0384

##### Additional Results for the Defense Algorithm \(Alg\.[3](https://arxiv.org/html/2606.11804#alg3)\)

We show several results for the performance of defense algorithm\.

Why Intermediateγ\\gammaValues Yield Smaller Loss\.The non\-monotonic behavior of the loss with respect toγ\\gammacan be understood from two extreme cases\. Whenγ→∞\\gamma\\to\\infty, the regularization term in Eq\.[4](https://arxiv.org/html/2606.11804#S3.E4)forces the weights𝐰\\mathbf\{w\}to become nearly uniform across attack types\. As a result, the update of𝐱\\mathbf\{x\}is affected almost equally by all attacks, which may lead to a more conservative solution and hence larger clean\-data loss\. In contrast, whenγ→0\\gamma\\to 0, the objective is dominated by the worst\-performing attack type, so that one weight tends to approach11while the others approach0\. In this case, the update of𝐱\\mathbf\{x\}is driven almost entirely by a single attack model, which may also degrade clean\-data performance\. Therefore, both extremes may increase the loss, while an intermediateγ\\gammaoften provides a better balance\.

Per\-model Results of the Robust Algorithm\.Besides the averaged metrics, we also report the objective values for each individual model under different settings\. From Tab\.[XXVIII](https://arxiv.org/html/2606.11804#A0.T28)to Tab\.[XXXVI](https://arxiv.org/html/2606.11804#A0.T36), the results consistently satisfyFp​\(𝐱¯T,Ωi\)≥Fprob​\(𝐱¯T,Ωi\)≥Fprob,att​\(𝐱¯T,Ωi​\(𝐯\)\)≥Fpatt​\(𝐱¯T,Ωi​\(𝐯\)\)\.F\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)\\geq F\_\{p\}^\{\\rm rob\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)\\geq F\_\{p\}^\{\\rm rob,att\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)\\geq F\_\{p\}^\{\\rm att\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)\.This shows that the robust algorithm introduces only moderate loss under clean data, while consistently improving over the attacked greedy solution under adversarial perturbations\. Hence, the per\-model results support the same conclusion as the averaged metrics: Alg\.[3](https://arxiv.org/html/2606.11804#alg3)provides effective robustness with acceptable utility loss\.

TABLE XXVIII:Objective valuesFFunderl1l\_\{1\}\-norm attacks withγ=0\.1\\gamma=0\.1\. Parameters:Krobust=100,Trobust=30,D=1K\_\{\\rm robust\}=100,T\_\{\\rm robust\}=30,D=1\)\.ModelFp​\(𝐱¯T,Ωi\)F\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob​\(𝐱¯T,Ωi\)F\_\{p\}^\{\\rm rob\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob,att​\(𝐱¯T,Ωi​\(𝐯\)\)F\_\{p\}^\{\\rm rob,att\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Fpatt​\(𝐱¯T,Ωi​\(𝐯\)\)F^\{\\rm att\}\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Model1\{\\rm Model\}\_\{1\}14\.775714\.297814\.091013\.6322Model2\{\\rm Model\}\_\{2\}14\.299613\.847013\.734513\.0018Model3\{\\rm Model\}\_\{3\}14\.382013\.814613\.706513\.1876Model4\{\\rm Model\}\_\{4\}13\.950213\.811113\.687413\.1219Model5\{\\rm Model\}\_\{5\}14\.059213\.613713\.572912\.8331Model6\{\\rm Model\}\_\{6\}14\.592514\.032113\.877613\.0850Model7\{\\rm Model\}\_\{7\}13\.949013\.816113\.690813\.2278Model8\{\\rm Model\}\_\{8\}14\.468614\.032213\.906113\.2038Model9\{\\rm Model\}\_\{9\}14\.520913\.996913\.809413\.3297Model10\{\\rm Model\}\_\{10\}14\.519413\.981713\.931413\.1609

TABLE XXIX:Objective valuesFFunderl2l\_\{2\}\-norm attacks withγ=0\.1\\gamma=0\.1\. Parameters:Krobust=100,Trobust=30,D=1K\_\{\\rm robust\}=100,T\_\{\\rm robust\}=30,D=1\.ModelFp​\(𝐱¯T,Ωi\)F\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob​\(𝐱¯T,Ωi\)F\_\{p\}^\{\\rm rob\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob,att​\(𝐱¯T,Ωi​\(𝐯\)\)F\_\{p\}^\{\\rm rob,att\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Fpatt​\(𝐱¯T,Ωi​\(𝐯\)\)F^\{\\rm att\}\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Model1\{\\rm Model\}\_\{1\}14\.775714\.297814\.128413\.2274Model2\{\\rm Model\}\_\{2\}14\.299613\.84713\.782813\.3292Model3\{\\rm Model\}\_\{3\}14\.38213\.814613\.780313\.3167Model4\{\\rm Model\}\_\{4\}13\.950213\.811113\.770713\.2822Model5\{\\rm Model\}\_\{5\}14\.059213\.613713\.607113\.0968Model6\{\\rm Model\}\_\{6\}14\.592514\.032113\.933713\.3608Model7\{\\rm Model\}\_\{7\}13\.94913\.816113\.77313\.3767Model8\{\\rm Model\}\_\{8\}14\.468614\.032213\.972113\.4204Model9\{\\rm Model\}\_\{9\}14\.520913\.996913\.914413\.3758Model10\{\\rm Model\}\_\{10\}14\.519413\.981713\.975913\.2969

TABLE XXX:Objective valuesFFunderl∞l\_\{\\infty\}\-norm attacks withγ=0\.1\\gamma=0\.1\. Parameters:Krobust=100,Trobust=30,D=0\.5K\_\{\\rm robust\}=100,T\_\{\\rm robust\}=30,D=0\.5\.ModelFp​\(𝐱¯T,Ωi\)F\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob​\(𝐱¯T,Ωi\)F\_\{p\}^\{\\rm rob\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob,att​\(𝐱¯T,Ωi​\(𝐯\)\)F\_\{p\}^\{\\rm rob,att\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Fpatt​\(𝐱¯T,Ωi​\(𝐯\)\)F^\{\\rm att\}\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Model1\{\\rm Model\}\_\{1\}14\.775714\.297814\.104813\.0891Model2\{\\rm Model\}\_\{2\}14\.299613\.84713\.732912\.949Model3\{\\rm Model\}\_\{3\}14\.38213\.814613\.714713\.0252Model4\{\\rm Model\}\_\{4\}13\.950213\.811113\.696212\.8062Model5\{\\rm Model\}\_\{5\}14\.059213\.613713\.572712\.7869Model6\{\\rm Model\}\_\{6\}14\.592514\.032113\.885413\.0343Model7\{\\rm Model\}\_\{7\}13\.94913\.816113\.694312\.8541Model8\{\\rm Model\}\_\{8\}14\.468614\.032213\.915713\.1074Model9\{\\rm Model\}\_\{9\}14\.520913\.996913\.8212\.9676Model10\{\\rm Model\}\_\{10\}14\.519413\.981713\.935313\.0981

TABLE XXXI:Objective valuesFFunderl1l\_\{1\}\-norm attacks withγ=1\\gamma=1\. Parameters:Krobust=100,Trobust=30,D=1\)K\_\{\\rm robust\}=100,T\_\{\\rm robust\}=30,D=1\)\.ModelFp​\(𝐱¯T,Ωi\)F\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob​\(𝐱¯T,Ωi\)F\_\{p\}^\{\\rm rob\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob,att​\(𝐱¯T,Ωi\)F\_\{p\}^\{\\rm rob,att\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fpatt​\(𝐱¯T,Ωi​\(𝐯\)\)F^\{\\rm att\}\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Model1\{\\rm Model\}\_\{1\}14\.775714\.229914\.094513\.6322Model2\{\\rm Model\}\_\{2\}14\.299613\.769713\.738813\.0018Model3\{\\rm Model\}\_\{3\}14\.38213\.860913\.721113\.1876Model4\{\\rm Model\}\_\{4\}13\.950213\.802113\.699513\.1219Model5\{\\rm Model\}\_\{5\}14\.059213\.624113\.571412\.8331Model6\{\\rm Model\}\_\{6\}14\.592514\.064213\.886713\.085Model7\{\\rm Model\}\_\{7\}13\.94913\.80613\.690713\.2278Model8\{\\rm Model\}\_\{8\}14\.468614\.059513\.91713\.2038Model9\{\\rm Model\}\_\{9\}14\.520914\.01213\.801613\.3297Model10\{\\rm Model\}\_\{10\}14\.519414\.036313\.922113\.1609

TABLE XXXII:Objective valuesFFunderl2l\_\{2\}\-norm attacks withγ=1\\gamma=1\. Parameters:Krobust=100,Trobust=30,D=1\)K\_\{\\rm robust\}=100,T\_\{\\rm robust\}=30,D=1\)\.ModelFp​\(𝐱¯T,Ωi\)F\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob​\(𝐱¯T,Ωi\)F\_\{p\}^\{\\rm rob\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob,att​\(𝐱¯T,Ωi​\(𝐯\)\)F\_\{p\}^\{\\rm rob,att\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Fpatt​\(𝐱¯T,Ωi​\(𝐯\)\)F^\{\\rm att\}\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Model1\{\\rm Model\}\_\{1\}14\.775714\.229914\.151213\.2274Model2\{\\rm Model\}\_\{2\}14\.299613\.769713\.797213\.3292Model3\{\\rm Model\}\_\{3\}14\.38213\.860913\.78813\.3167Model4\{\\rm Model\}\_\{4\}13\.950213\.802113\.760713\.2822Model5\{\\rm Model\}\_\{5\}14\.059213\.624113\.612613\.0968Model6\{\\rm Model\}\_\{6\}14\.592514\.064213\.955113\.3608Model7\{\\rm Model\}\_\{7\}13\.94913\.80613\.767213\.3767Model8\{\\rm Model\}\_\{8\}14\.468614\.059513\.96913\.4204Model9\{\\rm Model\}\_\{9\}14\.520914\.01213\.90813\.3758Model10\{\\rm Model\}\_\{10\}14\.519414\.036313\.986313\.2969

TABLE XXXIII:Objective valuesFFunderl∞l\_\{\\infty\}\-norm attacks withγ=1\\gamma=1\. Parameters:Krobust=100,Trobust=30,D=0\.5\)K\_\{\\rm robust\}=100,T\_\{\\rm robust\}=30,D=0\.5\)\.ModelFp​\(𝐱¯T,Ωi\)F\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob​\(𝐱¯T,Ωi\)F\_\{p\}^\{\\rm rob\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob,att​\(𝐱¯T,Ωi​\(𝐯\)\)F\_\{p\}^\{\\rm rob,att\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Fpatt​\(𝐱¯T,Ωi​\(𝐯\)\)F^\{\\rm att\}\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Model1\{\\rm Model\}\_\{1\}14\.775714\.229914\.109513\.0891Model2\{\\rm Model\}\_\{2\}14\.299613\.769713\.750712\.949Model3\{\\rm Model\}\_\{3\}14\.38213\.860913\.718113\.0252Model4\{\\rm Model\}\_\{4\}13\.950213\.802113\.709512\.8062Model5\{\\rm Model\}\_\{5\}14\.059213\.624113\.579912\.7869Model6\{\\rm Model\}\_\{6\}14\.592514\.064213\.891513\.0343Model7\{\\rm Model\}\_\{7\}13\.94913\.80613\.706112\.8541Model8\{\\rm Model\}\_\{8\}14\.468614\.059513\.92213\.1074Model9\{\\rm Model\}\_\{9\}14\.520914\.01213\.812612\.9676Model10\{\\rm Model\}\_\{10\}14\.519414\.036313\.932913\.0981

TABLE XXXIV:Objective valuesFFunderl1l\_\{1\}\-norm attacks withγ=10\\gamma=10\. Parameters:Krobust=100,Trobust=30,D=1\)K\_\{\\rm robust\}=100,T\_\{\\rm robust\}=30,D=1\)\.ModelFp​\(𝐱¯T,Ωi\)F\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob​\(𝐱¯T,Ωi\)F\_\{p\}^\{\\rm rob\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob,att​\(𝐱¯T,Ωi​\(𝐯\)\)F\_\{p\}^\{\\rm rob,att\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Fpatt​\(𝐱¯T,Ωi​\(𝐯\)\)F^\{\\rm att\}\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Model1\{\\rm Model\}\_\{1\}14\.775714\.057914\.025913\.6322Model2\{\\rm Model\}\_\{2\}14\.299613\.754413\.688913\.0018Model3\{\\rm Model\}\_\{3\}14\.38213\.654913\.675813\.1876Model4\{\\rm Model\}\_\{4\}13\.950213\.695313\.594513\.1219Model5\{\\rm Model\}\_\{5\}14\.059213\.554613\.541612\.8331Model6\{\\rm Model\}\_\{6\}14\.592513\.784313\.823813\.085Model7\{\\rm Model\}\_\{7\}13\.94913\.695113\.580613\.2278Model8\{\\rm Model\}\_\{8\}14\.468613\.88513\.914513\.2038Model9\{\\rm Model\}\_\{9\}14\.520913\.745213\.749513\.3297Model10\{\\rm Model\}\_\{10\}14\.519413\.916713\.873813\.1609

TABLE XXXV:Objective valuesFFunderl2l\_\{2\}\-norm attacks withγ=10\\gamma=10\. Parameters:Krobust=100,Trobust=30,D=1\)K\_\{\\rm robust\}=100,T\_\{\\rm robust\}=30,D=1\)\.ModelFp​\(𝐱¯T,Ωi\)F\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob​\(𝐱¯T,Ωi\)F\_\{p\}^\{\\rm rob\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob,att​\(𝐱¯T,Ωi​\(𝐯\)\)F\_\{p\}^\{\\rm rob,att\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Fpatt​\(𝐱¯T,Ωi​\(𝐯\)\)F^\{\\rm att\}\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Model1\{\\rm Model\}\_\{1\}14\.775714\.057914\.091413\.2274Model2\{\\rm Model\}\_\{2\}14\.299613\.754413\.746513\.3292Model3\{\\rm Model\}\_\{3\}14\.38213\.654913\.747713\.3167Model4\{\\rm Model\}\_\{4\}13\.950213\.695313\.691313\.2822Model5\{\\rm Model\}\_\{5\}14\.059213\.554613\.539713\.0968Model6\{\\rm Model\}\_\{6\}14\.592513\.784313\.795213\.3608Model7\{\\rm Model\}\_\{7\}13\.94913\.695113\.723813\.3767Model8\{\\rm Model\}\_\{8\}14\.468613\.88513\.952413\.4204Model9\{\\rm Model\}\_\{9\}14\.520913\.745213\.849613\.3758Model10\{\\rm Model\}\_\{10\}14\.519413\.916713\.921813\.2969

TABLE XXXVI:Objective valuesFFunderl∞l\_\{\\infty\}\-norm attacks withγ=10\\gamma=10\. Parameters:Krobust=100,Trobust=30,D=0\.5\)K\_\{\\rm robust\}=100,T\_\{\\rm robust\}=30,D=0\.5\)\.ModelFp​\(𝐱¯T,Ωi\)F\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob​\(𝐱¯T,Ωi\)F\_\{p\}^\{\\rm rob\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\)Fprob,att​\(𝐱¯T,Ωi​\(𝐯\)\)F\_\{p\}^\{\\rm rob,att\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Fpatt​\(𝐱¯T,Ωi​\(𝐯\)\)F^\{\\rm att\}\_\{p\}\(\\bar\{\\mathbf\{x\}\}\_\{T\},\\Omega\_\{i\}\(\\mathbf\{v\}\)\)Model1\{\\rm Model\}\_\{1\}14\.775714\.057914\.050813\.0891Model2\{\\rm Model\}\_\{2\}14\.299613\.754413\.781212\.949Model3\{\\rm Model\}\_\{3\}14\.38213\.654913\.740613\.0252Model4\{\\rm Model\}\_\{4\}13\.950213\.695313\.737412\.8062Model5\{\\rm Model\}\_\{5\}14\.059213\.554613\.533212\.7869Model6\{\\rm Model\}\_\{6\}14\.592513\.784313\.832113\.0343Model7\{\\rm Model\}\_\{7\}13\.94913\.695113\.668112\.8541Model8\{\\rm Model\}\_\{8\}14\.468613\.88513\.868613\.1074Model9\{\\rm Model\}\_\{9\}14\.520913\.745213\.747912\.9676Model10\{\\rm Model\}\_\{10\}14\.519413\.916713\.885213\.0981

## References

- \[1\]\(2022\)Minimax optimization: the case of convex\-submodular\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 3556–3580\.Cited by:[§\-E](https://arxiv.org/html/2606.11804#A0.SS5.SSS0.Px1.p2.1),[§I](https://arxiv.org/html/2606.11804#S1.p4.1),[§II\-A](https://arxiv.org/html/2606.11804#S2.SS1.p1.1),[TABLE I](https://arxiv.org/html/2606.11804#S2.T1.1.1.1.2),[TABLE I](https://arxiv.org/html/2606.11804#S2.T1.2.2.2.2),[§VI\-B1](https://arxiv.org/html/2606.11804#S6.SS2.SSS1.p2.1)\.
- \[2\]K\. Alex\(2009\)Learning multiple layers of features from tiny images\.https://www\. cs\. toronto\. edu/kriz/learning\-features\-2009\-TR\. pdf\.Cited by:[§\-E](https://arxiv.org/html/2606.11804#A0.SS5.p2.20),[§VI\-A1](https://arxiv.org/html/2606.11804#S6.SS1.SSS1.p1.3)\.
- \[3\]A\. A\. Bian, B\. Mirzasoleiman, J\. Buhmann, and A\. Krause\(2017\)Guaranteed non\-convex optimization: submodular maximization over continuous domains\.InArtificial Intelligence and Statistics,pp\. 111–120\.Cited by:[§\-A1](https://arxiv.org/html/2606.11804#A0.SS1.SSS1.p1.17),[§III\-A](https://arxiv.org/html/2606.11804#S3.SS1.p3.11),[Definition 1](https://arxiv.org/html/2606.11804#Thmdefinition1)\.
- \[4\]C\. Chekuri, J\. Vondrák, and R\. Zenklusen\(2011\)Submodular function maximization via the multilinear relaxation and contention resolution schemes\.InProceedings of the forty\-third annual ACM symposium on Theory of computing,pp\. 783–792\.Cited by:[§I](https://arxiv.org/html/2606.11804#S1.p2.1)\.
- \[5\]L\. Chen, Y\. Xu, F\. Xie, M\. Huang, and Z\. Zheng\(2021\)Data poisoning attacks on neighborhood\-based recommender systems\.Transactions on Emerging Telecommunications Technologies32\(6\),pp\. e3872\.Cited by:[§I](https://arxiv.org/html/2606.11804#S1.p3.1)\.
- \[6\]W\. Chen, T\. Lin, Z\. Tan, M\. Zhao, and X\. Zhou\(2016\)Robust influence maximization\.InProceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining,pp\. 795–804\.Cited by:[§II\-B](https://arxiv.org/html/2606.11804#S2.SS2.p1.1)\.
- \[7\]X\. He and D\. Kempe\(2018\)Stability and robustness in influence maximization\.ACM Transactions on Knowledge Discovery from Data \(TKDD\)12\(6\),pp\. 1–34\.Cited by:[§II\-B](https://arxiv.org/html/2606.11804#S2.SS2.p1.1)\.
- \[8\]V\. Kaushal, G\. Ramakrishnan, and R\. Iyer\(2022\)Submodlib: a submodular optimization library\.arXiv preprint arXiv:2202\.10680\.Cited by:[§I](https://arxiv.org/html/2606.11804#S1.p2.1)\.
- \[9\]A\. Krause, H\. B\. McMahan, C\. Guestrin, and A\. Gupta\(2008\)Robust submodular observation selection\.Journal of Machine Learning Research9\(12\)\.Cited by:[§II\-B](https://arxiv.org/html/2606.11804#S2.SS2.p1.1)\.
- \[10\]Y\. LeCun and C\. Cortes\(2010\)MNIST handwritten digit database\.Note:http://yann\.lecun\.com/exdb/mnist/External Links:[Link](http://yann.lecun.com/exdb/mnist/)Cited by:[§\-E](https://arxiv.org/html/2606.11804#A0.SS5.p2.20),[§VI\-A1](https://arxiv.org/html/2606.11804#S6.SS1.SSS1.p1.3)\.
- \[11\]D\. Lee, N\. Ho\-Nguyen, and D\. Lee\(2022\)Non\-smooth and holder\-smooth submodular maximization\.arXiv preprint arXiv:2210\.06061\.Cited by:[§\-E](https://arxiv.org/html/2606.11804#A0.SS5.SSS0.Px2.p4.1),[§I](https://arxiv.org/html/2606.11804#S1.p4.1),[§II\-B](https://arxiv.org/html/2606.11804#S2.SS2.p2.1),[TABLE I](https://arxiv.org/html/2606.11804#S2.T1.3.3.3.2)\.
- \[12\]Q\. Lei, L\. Wu, P\. Chen, A\. Dimakis, I\. S\. Dhillon, and M\. J\. Witbrock\(2019\)Discrete adversarial attacks and submodular optimization with applications to text classification\.Proceedings of Machine Learning and Systems1,pp\. 146–165\.Cited by:[§I](https://arxiv.org/html/2606.11804#S1.p4.1),[§II\-A](https://arxiv.org/html/2606.11804#S2.SS1.p1.1)\.
- \[13\]Y\. Lian, X\. Wang, D\. Xu, and Z\. Zhao\(2024\)Zeroth\-order stochastic approximation algorithms for dr\-submodular optimization\.Journal of Machine Learning Research25\(391\),pp\. 1–55\.Cited by:[§\-A1](https://arxiv.org/html/2606.11804#A0.SS1.SSS1.p3.2),[§\-E](https://arxiv.org/html/2606.11804#A0.SS5.SSS0.Px2.p4.1),[§I](https://arxiv.org/html/2606.11804#S1.p4.1),[§II\-B](https://arxiv.org/html/2606.11804#S2.SS2.p2.1),[TABLE I](https://arxiv.org/html/2606.11804#S2.T1.4.4.4.2)\.
- \[14\]T\. Lin, C\. Jin, and M\. Jordan\(2020\)On gradient descent ascent for nonconvex\-concave minimax problems\.InInternational Conference on Machine Learning,pp\. 6083–6093\.Cited by:[§\-C1](https://arxiv.org/html/2606.11804#A0.SS3.SSS1.p2.2)\.
- \[15\]Q\. Liu, C\. Zhao, M\. Liu, R\. Deng, and P\. Cheng\(2025\)Submodularity\-based false data injection attack strategy in dc microgrids\.IEEE Transactions on Information Forensics and Security20\(\),pp\. 2342–2356\.External Links:[Document](https://dx.doi.org/10.1109/TIFS.2025.3541381)Cited by:[§II\-A](https://arxiv.org/html/2606.11804#S2.SS1.p1.1)\.
- \[16\]L\. Lovász\(1983\)Submodular functions and convexity\.Mathematical Programming The State of the Art: Bonn 1982,pp\. 235–257\.Cited by:[§I](https://arxiv.org/html/2606.11804#S1.p2.1)\.
- \[17\]L\. Mualem and M\. Feldman\(2022\)Using partial monotonicity in submodular maximization\.Advances in Neural Information Processing Systems35,pp\. 2723–2736\.Cited by:[§III\-A](https://arxiv.org/html/2606.11804#S3.SS1.p2.5),[§III\-A](https://arxiv.org/html/2606.11804#S3.SS1.p3.11)\.
- \[18\]J\. Schreiber, J\. Bilmes, and W\. S\. Noble\(2020\)Apricot: submodular selection for data summarization in python\.Journal of Machine Learning Research21\(161\),pp\. 1–6\.Cited by:[§I](https://arxiv.org/html/2606.11804#S1.p2.1)\.
- \[19\]T\. Soma, N\. Kakimura, K\. Inaba, and K\. Kawarabayashi\(2014\)Optimal budget allocation: theoretical guarantee and efficient algorithm\.InInternational Conference on Machine Learning,pp\. 351–359\.Cited by:[§I](https://arxiv.org/html/2606.11804#S1.p2.1)\.
- \[20\]M\. Staib and S\. Jegelka\(2017\)Robust budget allocation via continuous submodular functions\.InInternational Conference on Machine Learning,pp\. 3230–3240\.Cited by:[§I](https://arxiv.org/html/2606.11804#S1.p4.1),[§II\-B](https://arxiv.org/html/2606.11804#S2.SS2.p1.1)\.
- \[21\]M\. Staib, B\. Wilder, and S\. Jegelka\(2019\)Distributionally robust submodular maximization\.InThe 22nd International Conference on Artificial Intelligence and Statistics,pp\. 506–516\.Cited by:[§II\-B](https://arxiv.org/html/2606.11804#S2.SS2.p1.1)\.
- \[22\]Y\. Suo, S\. Chai, R\. Chai, Z\. Pang, Y\. Xia, and G\. Liu\(2024\)Security defense of large\-scale networks under false data injection attacks: an attack detection scheduling approach\.IEEE Transactions on Information Forensics and Security19\(\),pp\. 1908–1921\.External Links:[Document](https://dx.doi.org/10.1109/TIFS.2023.3340098)Cited by:[§I](https://arxiv.org/html/2606.11804#S1.p2.1)\.
- \[23\]K\. K\. Thekumparampil, P\. Jain, P\. Netrapalli, and S\. Oh\(2019\)Efficient algorithms for smooth minimax optimization\.Advances in Neural Information Processing Systems32\.Cited by:[Definition 3](https://arxiv.org/html/2606.11804#Thmdefinition3)\.
- \[24\]G\. Tolias, F\. Radenovic, and O\. Chum\(2019\)Targeted mismatch adversarial attack: query with a flower to retrieve the tower\.InProceedings of the IEEE/CVF international conference on computer vision,pp\. 5037–5046\.Cited by:[§I](https://arxiv.org/html/2606.11804#S1.p3.1)\.
- \[25\]J\. Wang, T\. Zhang, S\. Liu, P\. Chen, J\. Xu, M\. Fardad, and B\. Li\(2021\)Adversarial attack generation empowered by min\-max optimization\.Advances in Neural Information Processing Systems34,pp\. 16020–16033\.Cited by:[§\-E](https://arxiv.org/html/2606.11804#A0.SS5.SSS0.Px1.p2.1),[§I](https://arxiv.org/html/2606.11804#S1.p4.1),[§II\-A](https://arxiv.org/html/2606.11804#S2.SS1.p1.1),[§II\-B](https://arxiv.org/html/2606.11804#S2.SS2.p2.1),[TABLE I](https://arxiv.org/html/2606.11804#S2.T1.6.6.8.1),[TABLE I](https://arxiv.org/html/2606.11804#S2.T1.6.6.9.1),[§VI\-B1](https://arxiv.org/html/2606.11804#S6.SS2.SSS1.p2.1)\.
- \[26\]B\. Wilder\(2018\)Equilibrium computation and robust optimization in zero sum games with submodular structure\.Proceedings of the AAAI Conference on Artificial Intelligence32\(1\)\.Cited by:[§II\-B](https://arxiv.org/html/2606.11804#S2.SS2.p1.1)\.
- \[27\]H\. Xiao, K\. Rasul, and R\. Vollgraf\(2017\)Fashion\-mnist: a novel image dataset for benchmarking machine learning algorithms\.External Links:1708\.07747Cited by:[§\-E](https://arxiv.org/html/2606.11804#A0.SS5.p2.20),[§VI\-A1](https://arxiv.org/html/2606.11804#S6.SS1.SSS1.p1.3)\.
- \[28\]Z\. Xu, H\. Zhang, Y\. Xu, and G\. Lan\(2023\)A unified single\-loop alternating gradient projection algorithm for nonconvex–concave and convex–nonconcave minimax problems\.Mathematical Programming201\(1\),pp\. 635–706\.Cited by:[Definition 3](https://arxiv.org/html/2606.11804#Thmdefinition3)\.
- \[29\]L\. Zhu, Q\. Bao, and Z\. Zhang\(2023\)Measures and optimization for robustness and vulnerability in disconnected networks\.IEEE Transactions on Information Forensics and Security18\(\),pp\. 3350–3362\.External Links:[Document](https://dx.doi.org/10.1109/TIFS.2023.3279979)Cited by:[§II\-A](https://arxiv.org/html/2606.11804#S2.SS1.p1.1)\.