Which Directions Matter? Sparse Design for Affine Robust Optimization
Pedro Chumpitaz-Flores1
My Duong1
arXiv:2606.14648v1 [cs.LG] 12 Jun 2026
1
Juan S. Borrero1
University of South Florida, Tampa, FL, USA
Abstract Robust machine learning and optimization rely on the uncertainty model choice. We investigate which uncertainty directions a model must cover when defined by a finite dictionary and a budget constraint. Selecting a subset forms an atomic uncertainty set with a closed form support function, yielding tractable robust programs for affine objectives. We propose a data-driven selection rule based on a coverage objective over evaluation directions, including gradients, adversarial perturbations, or shifts observed on held out data. We prove this objective is monotone and submodular, supporting a greedy method with a (1 − 1/e) approximation guarantee and a matching hardness barrier. We also provide a certificate bounding the loss from the selected subset and a radius calibration rule with out-of-sample control.
INTRODUCTION
Directional uncertainty often involves large families of perturbation directions, yet only a small subset influences the robust optimum. This paper investigates: Given a finite dictionary D = {di }N i=1 and a budget B, which directions recover the robustness of the full model? We address this through an atomic directional uncertainty family US (r) indexed by subsets S ⊆ [N ], a submodular support coverage surrogate for budget-constrained selection, and certificates linking directional coverage to the robust value gap. We further provide finite-sample radius calibration for out-of-sample feasibility. Our approach builds on robust optimization via uncertainty set design and support function reformulations [Ben-Tal and Nemirovski, 1998, El Ghaoui and Lebret, 1997, Bertsimas and Sim, 2004, Bertsimas et al., 2011], motivated by certi-
Coverage Design
Full Dictionary
D = {di}N i=1
1
Kaixun Hua1
Eval Directions T ≈ {q(x)}
max|S|≤B F (S; T )
Atomic Uncertainty Budget Constraint B
US (r)
s∈T
L2 Ball
Candidate Vectors Large set of perturbations
Greedy Alignment Find di that maximize support
(Signal + Decoys)
hU (s) = max⟨di , s⟩
min Φ[N ] (x) − | x {z }
Full Robustness
min ΦS (x) | x {z }
Sparse Approximation
Resulting Polytope conv({di }i∈S ∪ {0}) Directed robustness
≤ r · max ∆S (s) s∈Teval | {z } Deficit
Thm. 3.1: The robust value gap is controlled by the worst-case alignment deficit ∆S (s) on the relevant directions Teval (up to the ε-net term).
Figure 1: Sparse directional design via greedy support alignment. From a dictionary D of candidate perturbations containing signal and noise (left), the strategy (center) greedily identifies atoms di maximizing support alignment with evaluation directions T , such as gradients. This defines the atomic uncertainty set US (r) as a sparse polytope (right). Section 3 establishes selection submodularity and optimality, while the performance certificate (Theorem 3.1) ensures minimizing the alignment deficit ∆S on T recovers the robust value.
fied learning under structured perturbations [Szegedy et al., 2013, Goodfellow et al., 2014, Madry et al., 2018, Wong and Kolter, 2018, Raghunathan et al., 2018, Cohen et al., 2019, Engstrom et al., 2017]. Algorithmically, we employ monotone submodular maximization with cardinality constraints [Nemhauser et al., 1978, Krause and Golovin, 2014] and integrate a calibration layer inspired by conformal prediction coverage guarantees [Vovk et al., 2005, Shafer and Vovk, 2008, Lei et al., 2018, Romano et al., 2019]. The dictionary D comprises application-specific candidates, including gradients, adversarial directions at training points, domain shifts, or stress directions used in robust optimization. Our experiments instantiate D using synthetic shifts and classifier feature directions to study the micro-budget regime B ≪ N .
Contributions. We present a framework for designing budget-constrained directional uncertainty sets.
Under the compactness of X, minimizers of ΦS are guaranteed to exist.
• Conceptually: We frame directional robustness as a subset design problem over a finite dictionary, where a small direction set recovers the full model performance. • Technically: We introduce an atomic uncertainty family with a closed-form support function, deriving certificates that relate directional coverage to the robust value gap and providing finite-sample radius calibration for out-ofsample feasibility. • Empirically: We demonstrate that greedy selection based on support coverage outperforms random baselines in the micro-budget regime, recovering full model behavior with a minimal fraction of directions.
2
2.3
2.1
PROBLEM SETUP AND PERFORMANCE GAP ATOMIC SETS AND DICTIONARIES
We consider a finite dictionary D = {d1 , . . . , dN } ⊂ Rp augmented with the null atom d0 := 0, and denote the index set by [N ]0 := {0, 1, . . . , N }. For any subset S ⊆ [N ], let S0 := S ∪ {0}. We define the atomic set dependent on a radius r > 0 as n o X X US (r) := u = αi di : αi ≥ 0, αi ≤ r , (1) i∈S
hUS (s) =
sup ⟨u, s⟩ = r max ⟨di , s⟩ . i∈S0
u∈US (r)
AFFINE ROBUST OPTIMIZATION
We address a baseline robust optimization problem defined over a nonempty and compact domain X ⊆ Rn . Assumption 2.1 (Affine structure in u and regularity). There exist continuous functions b : X → R and q : X → Rp such that the objective satisfies f (x, u) = b(x) + ⟨u, q(x)⟩ for all pairs (x, u). Accordingly, the robust objective is ΦS (x) :=
S⊆[N ] |S|≤B
sup f (x, u) u∈US (r)
= b(x) + hUS q(x)
= b(x) + r max ⟨di , q(x)⟩ . i∈S0
(3)
x∈X
PERFORMANCE GAP AND CERTIFICATES
To quantify the loss of robustness, we define the full model corresponding to S = [N ] with objective Φ[N ] (x) = b(x) + r maxi∈[N ]0 ⟨di , q(x)⟩. The following result characterizes the difference between the full and restricted objectives. Proposition 2.3 (Pointwise value gap). For any x ∈ X and S ⊆ [N ], the value gap is given by Φ[N ] (x) − ΦS (x) = r max ⟨di , q(x)⟩ − max ⟨di , q(x)⟩ (5) i∈S i∈[N ]0
0
≥ 0.
In particular, if x⋆S is a minimizer of ΦS , then min Φ[N ] (x) − min ΦS (x) x
(2)
Although (1) relies on non-negative coefficients αi ≥ 0, symmetric uncertainty sets such as ℓ1 -balls are accommodated by including antipodal pairs {d, −d} in the dictionary D. 2.2
Given an out-of-sample evaluation metric Risk(x), such as the hold out violation rate or the conditional value at risk of the regret, the subset design problem seeks to minimize min Risk x⋆S where x⋆S ∈ Arg min ΦS (x). (4)
i∈S
which implies that the support function takes the closed form
Remark 2.2 (Optional convexity for tractability). If X is convex, b is convex, and q is affine, then the function x 7→ ΦS (x) is convex. This structure covers standard linear and second order cone programming instances by linearizing the maximum in the objective.
x
≤ Φ[N ] (x⋆S ) − ΦS (x⋆S ) = r ∆S q(x⋆S ) ,
where the deficit is defined as maxi∈[N ]0 ⟨di , s⟩ − maxi∈S0 ⟨di , s⟩.
∆S (s)
(6)
:=
Corollary 2.4 (Sufficient condition for equality of values). If there exists a solution x⋆S ∈ Arg min ΦS such that the deficit satisfies ∆S q(x⋆S ) = 0, then the optimal values coincide: min Φ[N ] (x) = min ΦS (x). x
x
We note that this does not imply coincidence of the minimizers except under additional properties such as uniqueness or strict convexity.
Remark 2.5 (Critical directions). We refer to the vectors st := q(xt ) as revealed directions, where xt is a solution of minx ΦSt (x) obtained during the algorithm described in Section 4.2. Monitoring the value ∆St (st ) allows us to certify the condition of Corollary 2.4 at run time.
3
THEORETICAL AND STATISTICAL GUARANTEES
3.1
DETERMINISTIC ERROR BOUNDS
Metric definitions. To establish a deterministic global bound on the value gap, we first recall the definition of the alignment deficit ∆S (s) := maxi∈[N ]0 ⟨di , s⟩ − maxi∈S0 ⟨di , s⟩ ≥ 0, where S0 = S ∪ {0} and [N ]0 = {0, 1, . . . , N } with d0 = 0. We introduce the pseudometric induced by the dictionary, defined as dD (s, s′ ) := max |⟨di , s − s′ ⟩|. i∈[N ]0
(7)
Based on this metric, a finite set T ⊂ Rp constitutes an ε-net of q(X) if, for every x ∈ X, there exists an element s ∈ T such that dD q(x), s ≤ ε. This geometric structure bridges the gap between discrete directional coverage and global robustness.
global value gap. While Theorem 4.5 ensures that the greedy strategy improves the average coverage F (S; T ), this certificate controls the worst-case deficit directly. In practice, we evaluate this certificate on sets built from revealed directions {q(xt )} and augmented with hold-out collections, reporting both the worst-case proxy and the average coverage. 3.2
FINITE SAMPLE FEASIBILITY
We complement the deterministic certificates with finitesample out-of-sample guarantees assuming independent and identically distributed samples {uj }m j=1 from the operational environment. Throughout this analysis, we use the P atomic set definition U (r) := {u = α di : αi ≥ S i i∈S P 0, i∈S αi ≤ r}. Directional statistic. For each subset S ⊆ [N ], define the directional score as ZS (u) := max ⟨di , u⟩. i∈S0
Theorem 3.1 (ε-net bridge theorem). Under Assumption 2.1 and compactness of X, for any subset S ⊆ [N ] and any ε-net T of q(X) in dD , the value gap satisfies min Φ[N ] (x) − min ΦS (x) ≤ r max ∆S (s) + 2ε . x
x
s∈T
Sketch (Full proof in App. D.3). For each x, the support function hU (q(x)) is r-Lipschitz in dD , meaning |hU (s) − hU (s′ )| ≤ r dD (s, s′ ). Taking s ∈ T with dD (q(x), s) ≤ ε and applying the inequality to both the full support and the restricted support yields Φ[N ] (x)−ΦS (x) ≤ r ∆S (s)+2ε . Minimizing over x and maximizing over s ∈ T concludes the proof.
Remark 3.2 (Constructing T via Lipschitzness of q). Let ∥ · ∥ be a norm on Rp with dual ∥ · ∥∗ and suppose q is Lq -Lipschitz on (X, ∥ · ∥), such that ∥q(x) − q(x′ )∥ ≤ Lq ∥x − x′ ∥. Since dD (s, s′ ) ≤ ∥D∥∗ ∥s − s′ ∥ with ∥D∥∗ := maxi∈[N ]0 ∥di ∥∗ , a grid in X with step ε ∆x ≤ ∥D∥∗ Lq ensures that the image T = {q(x) : x on the grid} is an ε-net in dD . In the linear case q(x) = M ⊤ x, we have Lq = ∥M ⊤ ∥ (operator norm induced by ∥ · ∥). An adaptive version starts from the revealed directions st = q(xt ) and refines partitions until the dD -diameter is at most ε.
In operational contexts, we maintain a set of evaluation directions T during the greedy procedure to compute the certificate gd ap(S; T , ε) := r(maxs∈T ∆S (s) + 2ε). By Theorem 3.1, this quantity deterministically upper-bounds the
Calibrating the radius r as a high quantile of ZS allows us to control the coverage level used by the pessimization oracle. b β (ZS ) denote the empirical β-quantile of the scores Let Q {ZS (uj )}m j=1 . For a confidence level 1 − δ, define s N 2 PB 1 k=0 k log . η := 2m δ
Assume η ≤ α. We then define the calibrated radius b 1−α+η (ZS ). rb(S) := Q
(8)
Theorem 3.3 (Finite-sample directional calibration). Assume η ≤ α. With probability at least 1 − δ over the sampling, the calibration (8) ensures that, simultaneously for every subset S ⊆ [N ] with |S| ≤ B, P ZS (U ) > r̂(S) ≤ α.
The full proof is provided in Appendix D.4. 3.3
RADIUS CALIBRATION PROCEDURE
The integration of this statistical layer into the greedy algorithm follows a sequential process. First, upon completion of the greedy selection which yields S, we compute the scores Z(uj ) = maxi∈S0 ⟨di , uj ⟩ for all samples j = 1, . . . , m. Second, we calibrate the radius rb according to (8). If the subset is fixed to exactly B,N the combinatorial term PB size N may be replaced by k=0 k B . Finally, we solve the robust optimization problem minx∈X ΦS (x) using the uncertainty set US (b r) to obtain the solution x⋆S . This procedure allows us to report both the finite-sample guarantee in Theorem 3.3 and the value gap performance certificate.
Conformal alternative. The correction term q statistical P N scales logarithmically as O( log which be/m), k comes modest when the sample size m is in the low thousands. For moderate sample sizes, a split-conformal calibration approach offers an alternative. By splitting the data into training (for selection) and an independent calibration set, one can define rb as the split-conformal quantile of Z, yielding exact marginal coverage for the event ZS (U ) ≤ rb without the logarithmic term, although this sacrifices uniformity over all data-dependent subsets. 3.4
4.2
ORACLE ASSISTED GREEDY METHOD
To address the design problem efficiently, we propose an iterative procedure that alternates between optimizing the robust objective and expanding the set of evaluation directions. At each iteration, the algorithm identifies a worst case perturbation for the current solution using an oracle on the full model. This revealed direction is added to the evaluation set, guiding the subsequent greedy selection of the dictionary atom that maximizes the marginal gain in support coverage.
VALIDATION PROTOCOL
The validation protocol requires partitioning the available data into training and hold-out sets. The training set is used to determine the subset S and, if applicable, to pre-calibrate the radius. The hold-out set is reserved to estimate the risk metric Risk(x⋆S ) for reporting purposes. Beyond the theoretical guarantees provided in Section 3.2, this protocol generates empirical summaries such as means, conditional value at risk, and violation rates. In our experiments, whenever calibration data is available, we apply the post-selection radius calibration step described above before reporting the final performance metrics.
4
GREEDY SELECTION ALGORITHM
4.1
SUPPORT COVERAGE OBJECTIVE
We begin by defining a finite set of evaluation directions T ⊂ Rp , which may consist of revealed directions {st } or a validation set. The support coverage functional is defined as the average maximum alignment over this set: F (S; T ) :=
1 X max ⟨di , s⟩ . i∈S0 |T |
(9)
s∈T
Proposition 4.1 (Submodularity and monotonicity of F ). For any fixed direction s ∈ T , the function gs (S) := maxi∈S0 ⟨di , s⟩ is monotone and submodular with respect to the set S. Since F is a non-negative linear combination of such functions, F (·; T ) retains both monotonicity and submodularity. This functional induces the surrogate design problem, denoted as (Pcov ), which captures the directional coverage properties of a subset S subject to a budget constraint: n o max F (S; T ) : |S| ≤ B . (Pcov )
Algorithm 1 Oracle assisted greedy for designing US (r) 1: Input: Dictionary D = {di }N i=1 , budget B, radius r
(later OOS calibrated to rb in Section 3.2), optional validation set V. 2: S ← ∅, T ← ∅. 3: for t = 1, . . . , B do 4: Solve xt ∈ Arg minx∈X ΦS (x) (convex if applicable). 5: Oracle on the full dictionary: obtain ut ∈ U[N ] (r) that approximately maximizes f (xt , u) (optional witness) With f (x, u) = b(x) + ⟨u, q(x)⟩, set 6: st ← q(xt ) (used for greedy scoring), At = arg maxi∈[N ]0 ⟨di , st ⟩, and update T ← T ∪ {st }. Choose it ∈ [N ] \ S that maximizes the marginal 7: gain of F (S ∪ {i}; T ). 8: S ← S ∪ {it }. 9: (Certifiable stopping) If ∆S (st ) = 0 and the best marginal gain in F is zero, stop. 10: (Optional) Early validation: stop if Risk(xt ) on V does not improve by more than ε. 11: end for 12: OOS calibration: compute rb as in Section 3.2 and re-solve minx∈X ΦS (x) with US (b r) to obtain x⋆S . ⋆ 13: Output: S, US (b r), and xS .
Remark 4.2 (Worst case greedy baseline). As a baseline that targets worst case coverage on the current direction set T , one can replace the selection rule in Algorithm 1 by it ∈ arg min max ∆S∪{i} (s). i∈[N ]\S
s∈T
S⊆[N ]
This problem abstracts the combinatorial core of our framework, where a larger value of F (S; T ) corresponds to superior average support coverage on the directions relevant to the robust optimization task.
This rule directly optimizes the certificate term maxs∈T ∆S (s), and we use it as a comparison point in experiments.
4.3
OPTIMALITY GUARANTEES
This section addresses the computational complexity of the design problem and the guarantees of the greedy approach. It first establishes computational hardness. Theorem 4.3 (NP hardness of directional coverage dep sign). Given a finite dictionary D = {di }N i=1 ⊂ R , a p finite set T ⊂ R , and a budget B, problem (Pcov ) is NP hard. This holds even when the coordinates of T and D are restricted to {0, 1}.
Corollary 4.6 (Approximation optimality of the greedy scheme). Combining Theorem 4.4 with Theorem 4.5, the greedy algorithm is approximation optimal for the directional coverage design problem under the standard assumption P ̸= N P . No polynomial time algorithm achieves a strictly better worst case approximation factor.
Sketch (Full proof in App. D.6). The proof reduces from the classical Max Coverage problem. Let U = {1, . . . , m} be the ground set and {Ai }N i=1 be subsets of U . An instance of (Pcov ) is constructed by setting p = m and identifying Rp with Rm . Each di is the indicator vector of Ai , and T is the set of canonical basis vectors. In this construction, maximizing F (S; T ) is equivalent to maximizing the cardinality of the union of the selected subsets, which is exactly Max Coverage.
Remark 4.7 (Selection objective and certification). The selection step optimizes the average coverage surrogate F because it is monotone and submodular, which gives the tight greedy guarantee in Theorem 4.5. The robust value gap, however, is certified through the worst case deficit maxs∈T ∆S (s) via the ε net bridge in Theorem 3.1. This distinction is explicit in the reported metrics: the algorithm optimizes F and reports the certificate term a posteriori. Appendix E provides a finite probe set bridge between these quantities. In particular, Proposition E.1 bounds the worst case deficit on T by the surrogate gap F ([N ]; T ) − F (S; T ) plus a probe set occupancy term and a resolution term, and Corollary E.2 combines this bound with Theorem 3.1 to obtain a robust value gap bound in terms of the surrogate gap.
The reduction is gap preserving, which yields a hardness of approximation result. 4.4 Theorem 4.4 (Hardness of approximation). For every ε > 0, unless P = N P , there is no polynomial time algorithm that, given an instance of (Pcov ), produces a subset S with |S| ≤ B satisfying F (S; T ) ≥ (1 − 1/e + ε) F (S ⋆ ; T ), where S ⋆ is an optimal solution.
Sketch (Full proof in App. D.7). Max Coverage is NP hard to approximate within any factor strictly larger than 1 − 1/e. Since the reduction preserves objective values up to a constant factor, any algorithm that exceeds this ratio for (Pcov ) would contradict the known hardness of Max Coverage. Despite these hardness results, the submodularity of F implies that the greedy algorithm attains the optimal approximation factor. Theorem 4.5 ((1 − 1/e) guarantee for greedy on F ). Under the constraint |S| ≤ B, the greedy algorithm that iteratively adds the index with the largest marginal increase in F (·; T ) satisfies F (Sgreedy ; T ) ≥ (1 − 1/e) F (S ⋆ ; T ), where S ⋆ maximizes F (·; T ) subject to the budget constraint.
COMPUTATIONAL COMPLEXITY
The proposed method is tractable for standard convex problems. By the support representation in (2), the objective ΦS (x) = b(x) + r max ⟨di , q(x)⟩ i∈S0
allows the minimization in line 3 of Algorithm 1 to be formulated as a convex problem whose size grows linearly with |S| (for example, by linearizing the maximum in LP or SOCP instances). The pessimization step over [N ] reduces to support evaluation or an equivalent dual computation, and the selection step computes marginal gains of F over T , which is inexpensive once the probe set is fixed.
5
COMPUTATIONAL EXPERIMENTS
Uncertainty directions come from a finite dictionary D = p {di }N i=1 ⊂ R . Given a budget B, each method selects a subset S ⊆ {1, . . . , N } with |S| ≤ B, which defines the atomic uncertainty set US (r) (Section 2.1). A common evaluation pipeline is used across settings. In Frozen Features, each method selects S and evaluates certified robustness at a fixed threat radius ε (Appendix H) without radius calibration. Unless noted, results are averaged over random seeds, and calibrated settings use fixed (α, δ). For each method, the evaluation direction set Teval combines directions revealed by the oracle based procedure
(Algorithm 1) with a held out pool when available. The reported metrics are the average coverage F (S; Teval ) and the proxy worst case s∈Teval
where ∆S (s) = max ⟨di , s⟩ − max⟨di , s⟩, i∈[N ]0
i∈S0
S0 = S ∪ {0}, [N ]0 = {0, 1, . . . , N }, d0 = 0.
The radius is set to reval = rb in calibrated settings and reval = ε in Frozen Features.
Baselines include Greedy, Random, MaxNorm, and Greedy MaxGap, the minimax rule of Remark 4.2 that targets maxs∈T ∆S (s) on the current direction set. In Section 5.1, we also report TopAct and a Mahalanobis ellipsoid fit. Random selects B atoms uniformly without replacement from D, and we report the mean and standard deviation over K independent draws. Selection cost is reported through B, wall clock time, oracle calls, and ρ = B/N . Oracle methods use at most B oracle queries by construction. Runtime includes robust solves and selection overhead under fixed solver and hardware settings (Appendix H).
1.5 1.0 0.5 0.0 3
Figure 2 reports the support error zfull − zS in direction xeval . Greedy Coverage and TopAct reduce the error at small budgets by selecting atoms with large projection onto xeval . Random improves more slowly because part of the budget is spent on decoys. MaxNorm performs poorly because decoys have large norms but contribute little support in direction xeval . Greedy MaxGap reduces a proxy worst case criterion on T and typically requires larger budgets to match average coverage. Figure 3 illustrates the mechanism. With small B, the atomic polytope can be anisotropic because it uses a small set of selected atoms to match support in relevant directions. The ellipsoidal baseline summarizes the distribution globally and can be conservative in direction xeval when decoys inflate dispersion.
7
9
11
13
15
17 19 Budget B
21
23
25
27
29
31
Geometry of Learned Uncertainty Sets
4
Dictionary Signal samples Ellipsoid Greedy polytope (B=3)
3 2 1 0
SYNTHETIC GEOMETRIC VALIDATION
This experiment isolates directional design in two dimensions. An X-shaped distribution is constructed and the dictionary is augmented with vertical decoy atoms that have large norm but low alignment with the evaluation direction. Uncertainty vectors u ∈ R2 are sampled near the diagonals, D is built from signal atoms and decoys, and the full dictionary support is compared with the restricted support induced by subsets S of size B in direction xeval = (1, 0) at unit radius. Greedy Coverage and Greedy MaxGap are evaluated on a fixed direction pool T , together with Random nested subsets, MaxNorm, and TopAct. A Mahalanobis ellipsoid fit on calibration samples is included as a convex baseline.
5
Figure 2: Support approximation error. Error versus budget B in direction xeval .
1 2 3 4
4
3
2
1
0
1
2
3
4
Figure 3: Geometry of learned uncertainty sets. Atomic polytope induced by S versus an ellipsoidal baseline.
Calibrated Radius (Union Bound) 4.0 3.5 Calibrated radius r(B)
5.1
Greedy-Coverage (Ours) Greedy-MaxGap (Ours) TopAct MaxNorm Random (mean) Ellipsoid conservatism
2.0 zfull zS (at r = 1, xeval = (1, 0))
G(S; Teval ) := reval max ∆S (s),
Support Approximation Error (Fixed Direction)
3.0 2.5 2.0 1.5
Greedy-Coverage (Ours) Greedy-MaxGap (Ours) TopAct MaxNorm Random (mean)
1.0 0.5 3
5
7
9
11
13
15
17 19 Budget B
21
23
25
27
29
31
Figure 4: Calibrated radius. Calibrated rb(B) versus budget B under DKW union calibration.
Figure 4 reports rb (B). As B increases, the union bound correction grows with the number of candidate subsets, so rb (B) increases after the empirical quantile stabilizes. Appendix H compares DKW union and split calibration and reports sweeps over (α, δ) with test split violations. DKW union remains conservative, with mean violation gap viold − α ∈ [−0.0086, −0.0082] across the tested δ, while split calibration is mildly anti conservative, with mean gap in [0.0037, 0.0048]; see Tables 5 and 6 and Figure 7. 5.2
not reach the target within the tested range B ≤ 50. Table 1 lists the corresponding budgets and reports an extrapolated estimate for Random, since it does not reach the target for B ≤ Bmax .
SCALING OF CERTIFIED COVERAGE WITH LARGE DICTIONARIES
We study directional selection with large uncertainty dictionaries in high ambient dimension. To keep training convex, we train linear robust classifiers on frozen features extracted from a pretrained convolutional network. We consider binary tasks built from CIFAR-10 and CIFAR-100, and report results in two regimes: Hard tasks from CIFAR-10 and Expert tasks from CIFAR-100. The appendix lists all task pairs and additional diagnostics. For each task and seed, we split data into disjoint sets for fitting, direction selection, reporting, and final testing. We mine a candidate dictionary D = {di }N i=1 by projected gradient ascent in feature space under an ℓ2 radius ε. We evaluate scaling with dictionary size by measuring coverage as a function of the budget density ρ = B/N . Figure 5 reports coverage versus ρ for multiple values of N . At matched density, Greedy maintains coverage as N increases, while Random degrades. This gap grows with N , consistent with a haystack effect in which random selection allocates budget to directions that do not contribute to the coverage objective.
Figure 6: Minimum B needed to reach coverage ≥ 0.990 as a function of dictionary size N . Random does not reach the target for B ≤ 50. Table 1: Minimum budget for target coverage (τ = 0.99). Greedy reaches the target with small budgets (B ≤ 20), while Random requires orders of magnitude more (extrapolated estimates ∗ ). Dict. Size (N )
Target
Bmax
Greedy B
Random B (Est.)
2,000 5,000 10,000 15,000
0.99 0.99 0.99 0.99
50 50 50 50
10 15 20 30
9, 208∗ 23, 023∗ 46, 049∗ 69, 075∗
∗
5.3
Extrapolated via coupon collector approximation.
BUDGET EFFICIENCY AND RELIABILITY ANALYSIS
The synthetic construction follows Lozano and Borrero [2025] with modifications for uncertainty set selection. The dimensions are n = q = 30 and m = p = 3, and problem tightness is controlled by rhs = 0.9, where lower values correspond to tighter constraints. Each instance is generated from a random seed.
Figure 5: Coverage versus budget density. Median coverage over tasks and seeds as a function of ρ = B/N , shown for multiple dictionary sizes N . To express these trends as a cost, we fix a target coverage level and report the smallest budget B that reaches the target. Figure 6 shows that Greedy reaches coverage ≥ 0.990 with budgets that increase slowly with N , while Random does
A total of 100 instances are generated, of which 64 instances (64.0%) are robust feasible under the full dictionary baseline, with zero violations. The onset budget and budget-wise efficiency analyses focus on this subset to isolate budget efficiency from baseline infeasibility. Appendix H.5 reports certification counts over all 100 instances. Three deterministic policies (greedy-maxgap, greedycoverage, and max-gamma) are compared with a random baseline. Efficiency is measured by the onset budget B ⋆ , the minimum budget that achieves zero violations.
Table 2: Deterministic robustness rate across budgets: percentage of the 64 seeds feasible under the full dictionary baseline with zero violations. Policy
B=1
2
3
5
7
10
15
20
30
greedy-maxgap greedy-coverage max-gamma
40.6 40.6 28.1
51.6 54.7 26.6
56.2 59.4 29.7
59.4 62.5 37.5
56.2 62.5 46.9
54.7 54.7 42.2
53.1 45.3 35.9
42.2 34.4 29.7
39.1 34.4 31.2
Table 2 reports zero-violation rates across budgets, and Table 3 summarizes B ⋆ over the same 64 instances. Success rates are not monotonic in B because each budget level is solved independently and the selected sets are not nested. Both greedy-maxgap and greedy-coverage reach a median onset of B ⋆ = 2, compared to 7 for max-gamma; within the evaluated budget grid, greedy-maxgap certifies 58 of 64 instances. Table 3: Onset of certified robustness (B ⋆ ) on seeds feasible under the full dictionary baseline (N = 64). Robust Rate reports the number of instances with zero violations within the evaluated budget grid. Mean and standard deviation are computed over instances that achieve robustness. Robust Rate Median B ⋆ Mean ± Std.
Policy greedy-maxgap greedy-coverage max-gamma
58/64 55/64 53/64
6.3 ± 8.3 6.3 ± 9.5 9.7 ± 10.0
2 2 7
The random baseline has no deterministic guarantee at a fixed budget, so reliability is evaluated with 50 independent repetitions per instance. Table 4 reports the mean success rate across the 64 instances feasible under the full dictionary baseline, together with the standard deviation across instances. The dispersion remains large across budgets, including larger values of B. Table 4: Reliability of the Random baseline on instances feasible under the full dictionary baseline (N = 64). For each budget B, success is the fraction of repetitions with zero violations, and the table reports the mean and standard deviation across instances. B Reps/seed Success (%) Std
6
3
5
7
10
15
50 22.9 ± 22.8
50 37.2 ± 29.8
50 46.7 ± 33.1
50 60.1 ± 33.6
50 69.8 ± 33.1
DISCUSSION
How does informed selection compare to uninformed baselines? Across geometric validation (Section 5.1) and scaling benchmarks (Section 5.2), greedy policies reduce support approximation error by aligning selected atoms with
the evaluation directions that drive the support function. Random selection spends budget on decoys or irrelevant constraints (Figure 2), weakening coverage and amplifying the haystack effect as the dictionary grows (Figure 5). How should the ε net term in the value certificate be interpreted? Theorem 3.1 decomposes the robust value gap into a discrete alignment deficit on a finite probe set T and a discretization term 2ε. Practical performance depends on the alignment term maxs∈T ∆S (s) and on how well T approximates q(X). Appendix H.3 introduces a proxy ε̂(T ) and a stopping rule based on the empirical certificate maxs∈T ∆S (s) + 2ε̂(T ), making the bound usable with finite probe pools. Appendix G shows that this certificate remains informative under inexact selection and inexact oracle evaluations. Does this efficiency translate to integer robust optimization? In integer programming (Section 5.3), Greedy MaxGap certifies robustness for most robust feasible instances with smaller budgets than max-gamma (Table 3). This pattern indicates that feasibility is often driven by a small set of active constraints that the greedy objective identifies. Why are success rates not monotonic? Success rates fluctuate because each budget is solved independently (Table 2). Larger budgets explore new combinations of scenarios rather than extending earlier selections, so rates can decrease at some levels and improve at others. A nested budget schedule would recover monotonicity if required. Is random selection a viable heuristic? Table 4 shows substantial variance for random selection even at larger budgets, with inconsistent certification across runs. Random selection is a high variance heuristic, while greedy policies provide deterministic guarantees with small sets.
7
CONCLUSIONS
The paper presents a framework for directional uncertainty sets from a finite dictionary. It formulates design as a submodular coverage problem, yielding a greedy method with approximation guarantees and tractability. The framework also provides finite-sample guarantees for radius calibration. Experiments show robust direction selection from large dictionaries, stable coverage in high dimensions, and small budget certification in integer programs.
References Aharon Ben-Tal and Arkadi Nemirovski. Robust convex optimization. Mathematics of operations research, 23(4): 769–805, 1998. Dimitris Bertsimas and Melvyn Sim. The price of robustness. Operations research, 52(1):35–53, 2004. Dimitris Bertsimas, David B Brown, and Constantine Caramanis. Theory and applications of robust optimization. SIAM review, 53(3):464–501, 2011. Giuseppe Carlo Calafiore and Marco C Campi. The scenario approach to robust control design. IEEE Transactions on automatic control, 51(5):742–753, 2006. Marco C Campi and Simone Garatti. The exact feasibility of randomized solutions of uncertain convex programs. SIAM Journal on Optimization, 19(3):1211–1230, 2008.
Andreas Krause and Daniel Golovin. Submodular function maximization. Tractability, 3(71-104):3, 2014. Jing Lei, Max G’Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 113(523):1094–1111, 2018. Leonardo Lozano and Juan S Borrero. On solving integer robust optimization problems with integer decisiondependent uncertainty sets: L. lozano, js borrero. Mathematical Programming, pages 1–33, 2025. Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018. URL https://openreview.net/forum? id=rJzIBfZAb.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In international conference on machine learning, pages 1310–1320. PMLR, 2019.
Baharan Mirzasoleiman, Amin Karbasi, Ashwinkumar Badanidiyuru, and Andreas Krause. Distributed submodular cover: Succinctly summarizing massive data. Advances in Neural Information Processing Systems, 28, 2015.
Laurent El Ghaoui and Hervé Lebret. Robust solutions to least-squares problems with uncertain data. SIAM Journal on matrix analysis and applications, 18(4):1035–1064, 1997.
Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. Advances in neural information processing systems, 29, 2016.
Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. A rotation and a translation suffice: Fooling cnns with simple transformations. 2017.
George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions—i. Mathematical programming, 14(1):265–294, 1978.
Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634–652, 1998.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In International Conference on Learning Representations, 2018. URL https://openreview.net/forum? id=Bys4ob-Rb.
Marc Goerigk and Mohammad Khosravi. Optimal scenario reduction for one-and two-stage robust optimization with discrete uncertainty in the objective. European Journal of Operational Research, 310(2):529–551, 2023. Marc Goerigk and Jannis Kurtz. Data-driven prediction of relevant scenarios for robust combinatorial optimization. Computers & Operations Research, 174:106886, 2025. Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014. Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1321–1330. PMLR, 06–11 Aug 2017. URL https://proceedings.mlr.press/v70/ guo17a.html.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Advances in neural information processing systems, 32, 2019. Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018. URL https://openreview.net/forum? id=H1aIuk-RW. Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008. Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. International Conference on Learning Representations, 2018.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013. Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer, 2005. Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International conference on machine learning, pages 1954–1963. PMLR, 2015. Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International conference on machine learning, pages 5286–5295. PMLR, 2018. Huan Xu, Constantine Caramanis, and Shie Mannor. Robustness and regularization of support vector machines. Journal of machine learning research, 10(7), 2009. Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass probability estimates. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 694–699, 2002.
Which Directions Matter? Sparse Design for Affine Robust Optimization (Supplementary Material)
Pedro Chumpitaz-Flores1
My Duong1 1
Juan S. Borrero1
Kaixun Hua1
University of South Florida, Tampa, FL, USA
A
RELATED WORK
A.1
SCENARIO-BASED ROBUST OPTIMIZATION
Robust optimization studies worst case decision making under uncertainty and provides tractable reformulations for broad classes of programs through uncertainty sets and their support functions [Ben-Tal and Nemirovski, 1998, El Ghaoui and Lebret, 1997]. When uncertainty is complex, a common alternative is to approximate it with a finite set of representative scenarios. This scenario approach samples constraints and yields finite sample guarantees for chance constrained problems [Calafiore and Campi, 2006, Campi and Garatti, 2008]. Recent work studies scenario reduction for one and two stage robust optimization with discrete uncertainty and derives approximation guarantees that hold for any reduced uncertainty set [Goerigk and Khosravi, 2023]. Related work proposes data-driven rules to identify relevant scenarios that produce strong bounds early in iterative constraint or variable generation methods for robust combinatorial optimization [Goerigk and Kurtz, 2025]. These results provide certificates for probabilistic constraint satisfaction or for approximation quality and convergence speed under scenario reduction. They do not provide selection aware certificates that quantify how a reduced representation deviates from a richer directional robust model, such as computable bounds on the robust value gap induced by selecting a subset of directions. A.2
ADVERSARIAL ROBUST LEARNING
Robust optimization has influenced robust learning in several forms. Robust support vector machines relate robust losses to regularization [Xu et al., 2009], and distributionally robust learning formalizes robustness to distribution shift [Namkoong and Duchi, 2016, Sinha et al., 2018]. The study of adversarial examples [Szegedy et al., 2013] led to adversarial training, which can be written as a robust optimization problem over norm bounded perturbations [Goodfellow et al., 2014, Madry et al., 2018]. To reduce cost or conservatism, structured perturbation families have been considered, including geometric transformations [Engstrom et al., 2017]. Certified defenses provide worst case guarantees for specific perturbation classes, including convex relaxation methods [Wong and Kolter, 2018], semidefinite bounds [Raghunathan et al., 2018], and randomized smoothing [Cohen et al., 2019]. Most of this literature treats the perturbation family as fixed or learned end to end. In contrast, the present setting selects a small subset from a large, pre specified dictionary of candidate directions and provides an explicit certificate for the approximation loss relative to the full directional model. A.3
SUBMODULAR SUBSET SELECTION
The selection problem is closely connected to submodular optimization. Many coverage objectives are monotone and submodular, and greedy algorithms achieve approximation guarantees in this setting. The classical result of Nemhauser et al. [1978] shows that greedy attains a (1 − 1/e) factor for monotone submodular maximization under a cardinality constraint, and that this factor is tight under standard complexity assumptions. Submodularity has been used for data subset selection and active learning [Wei et al., 2015], as well as for large scale variants based on distributed and streaming computation
[Mirzasoleiman et al., 2015]. Surveys also cover sensing and information gathering objectives [Krause and Golovin, 2014]. Related work on coresets selects representative points for learning objectives [Sener and Savarese, 2018]. The central difficulty here is not only to optimize a combinatorial objective, but to identify a coverage functional whose value directly upper bounds robust degradation. The selected objects are uncertainty directions rather than data points, while the resulting optimization follows the same greedy principle once the appropriate functional is defined. A.4
CALIBRATION AND CONFORMAL GUARANTEES
After selecting directions, the radius of the uncertainty set must be calibrated. Small radii may under protect, whereas large radii may be overly conservative. Calibration of probabilistic outputs is widely studied in prediction systems [Zadrozny and Elkan, 2002, Guo et al., 2017]. Conformal prediction provides distribution free finite sample coverage guarantees by calibrating a score on held out data [Vovk et al., 2005, Shafer and Vovk, 2008], with developments for regression and quantile based intervals [Lei et al., 2018, Romano et al., 2019]. Conformal robust optimization yields finite sample coverage certificates for uncertainty sets, but typically does not address the representation problem of selecting which candidate directions to retain, nor provide a deterministic certificate for how selection changes the robust objective. The radius calibration in this work targets a prescribed out-of-sample coverage level for the robust solution, complementing the deterministic selection aware certificate.
B
SCOPE AND LIMITATIONS.
Our framework focuses on affine robust optimization with finite dictionaries. While the design problem is NP-hard, our submodular formulation ensures the greedy strategy provides a strong approximation. The primary limitation is the dependence on the input dictionary; if the candidate pool lacks the true worst-case directions, the resulting set will be optimistic. Therefore, the method is best combined with high-recall mining procedures or domain knowledge. Future work will extend this approach to end-to-end dictionary learning and non-affine uncertainty structures.
C
BROADER IMPACT.
This framework supports reliability oriented decision making in settings where structured perturbations matter, such as planning and risk sensitive prediction. It can increase conservatism and reduce performance for some groups if the dictionary reflects biased data or incomplete domain knowledge. The dictionary, budget, and calibration target encode which shifts are treated as relevant. We recommend documenting these choices, reporting selected directions, sensitivity to budget and radius, and evaluating coverage on held out data.
D
PROOF OF THEOREMS
D.1
PROOF OF PROPOSITION 2.3
Proof. Recall ΦS (x) = b(x) + r max⟨di , q(x)⟩, i∈S0
Therefore, for every x ∈ X, Φ[N ] (x) − ΦS (x) = r
Φ[N ] (x) = b(x) + r max ⟨di , q(x)⟩. i∈[N ]0
max ⟨di , q(x)⟩ − max⟨di , q(x)⟩
i∈[N ]0
i∈S0
= r ∆S (q(x)), which is the claimed identity. D.2
PROOF OF COROLLARY 2.4
Proof. Let x⋆S ∈ arg minx ΦS (x). By Proposition 2.3, Φ[N ] (x⋆S ) − ΦS (x⋆S ) = r ∆S (q(x⋆S )).
If ∆S (q(x⋆S )) = 0, then Φ[N ] (x⋆S ) = ΦS (x⋆S ). Also, ∆S (·) ≥ 0, so Proposition 2.3 implies Φ[N ] (x) ≥ ΦS (x)
∀x ∈ X.
Hence min Φ[N ] (x) ≥ min ΦS (x) = ΦS (x⋆S ) = Φ[N ] (x⋆S ) ≥ min Φ[N ] (x), x
x
x
which proves min Φ[N ] (x) = min ΦS (x). x
D.3
x
PROOF OF THEOREM 3.1
Proof. For any index set A ⊆ [N ]0 , define s ∈ Rp .
MA (s) := max ⟨di , s⟩ , i∈A
Then ∆S (s) = M[N ]0 (s) − MS0 (s).
We first record a Lipschitz property (with respect to dD ): for any A ⊆ [N ]0 and any s, s′ ∈ Rp , |MA (s) − MA (s′ )| ≤ max |⟨di , s − s′ ⟩| ≤ max |⟨di , s − s′ ⟩| = dD (s, s′ ). i∈A
i∈[N ]0
Indeed, for any i ∈ A, ⟨di , s⟩ ≤ ⟨di , s′ ⟩+| ⟨di , s − s′ ⟩ |, so taking maxima over i ∈ A gives MA (s) ≤ MA (s′ )+dD (s, s′ ); exchanging s, s′ yields the reverse inequality. Now fix an arbitrary x ∈ X. Since T is an ε-net of q(X) in dD , there exists t = t(x) ∈ T such that dD (q(x), t) ≤ ε. Using the previous Lipschitz bound for both A = [N ]0 and A = S0 , ∆S (q(x)) = M[N ]0 (q(x)) − MS0 (q(x)) ≤ M[N ]0 (t) + ε − MS0 (t) − ε = ∆S (t) + 2ε
≤ max ∆S (s) + 2ε. s∈T
By Proposition 2.3 (pointwise value gap), for every x ∈ X, Φ[N ] (x) − ΦS (x) = r ∆S (q(x)). Therefore,
Φ[N ] (x) − ΦS (x) ≤ r max ∆S (s) + 2ε . s∈T
This bound holds for every x ∈ X. In particular, if x⋆S ∈ arg minx ΦS (x), then min Φ[N ] (x) − min ΦS (x) ≤ Φ[N ] (x⋆S ) − ΦS (x⋆S ) x x ≤ r max ∆S (s) + 2ε , s∈T
which proves the theorem.
D.4
PROOF OF THEOREM 3.3
Proof. Let MB :=
B X N . k
k=0
Fix a subset S ⊆ [N ] with |S| ≤ B. Let FS denote the population CDF of ZS (U ), and let FbS be its empirical CDF based on {Uj }m j=1 . By the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality, for each fixed S, 2 δ P sup FbS (z) − FS (z) > η ≤ 2e−2mη = . MB z∈R Define the event
ES := Then P(ES ) ≥ 1 − δ/MB .
sup FbS (z) − FS (z) ≤ η . z∈R
Now take a union bound over all subsets S ⊆ [N ] with |S| ≤ B. The event \ E := ES S⊆[N ] |S|≤B
satisfies P(E) ≥ 1 −
X
S⊆[N ] |S|≤B
δ ≥ 1 − δ. MB
We now prove the claimed guarantee on the event E. Fix any S ⊆ [N ] with |S| ≤ B, and set
By definition of the empirical quantile,
b 1−α+η (ZS ). r := rb(S) = Q FbS (r) ≥ 1 − α + η.
Since E implies FbS (z) − FS (z) ≤ η for all z, we obtain
FS (r) ≥ FbS (r) − η ≥ 1 − α.
Therefore,
P(ZS (U ) > r) = 1 − FS (r) ≤ α. Because this argument is valid for every S with |S| ≤ B, the guarantee holds simultaneously for all such subsets on the event E. Finally, the subset returned by Algorithm 1 is data-dependent, but it belongs to the same finite family {S ⊆ [N ] : |S| ≤ B}. Hence the same simultaneous guarantee applies to the algorithm output. D.5
PROOF OF PROPOSITION 4.1
Proof. Fix s ∈ T and define
gs (S) := max⟨di , s⟩. i∈S0
Monotonicity is immediate: if A ⊆ B, then A0 ⊆ B0 , hence gs (A) = max⟨di , s⟩ ≤ max⟨di , s⟩ = gs (B). i∈A0
i∈B0
To show submodularity, let A ⊆ B ⊆ [N ] and j ∈ [N ] \ B. Write aj := ⟨dj , s⟩. Then gs (A ∪ {j}) − gs (A) = max{gs (A), aj } − gs (A) = max{0, aj − gs (A)}, and similarly gs (B ∪ {j}) − gs (B) = max{0, aj − gs (B)}. Since gs (A) ≤ gs (B), we get
max{0, aj − gs (A)} ≥ max{0, aj − gs (B)},
which is the diminishing-returns property. Thus gs is submodular. Finally, F (S; T ) =
1 X gs (S) |T | s∈T
is a nonnegative linear combination of monotone submodular functions, hence is itself monotone and submodular.
D.6
PROOF OF THEOREM 4.3
Proof. We reduce from the classical Max-Coverage problem. An instance of Max-Coverage consists of: • a ground set U = {1, . . . , m}, • subsets A1 , . . . , AN ⊆ U , • a budget B,
and asks for a set of indices S ⊆ [N ] with |S| ≤ B maximizing [
Ai .
i∈S
Given such an instance, construct an instance of the directional coverage problem as follows: • Set the ambient dimension to p = m. • For each i ∈ [N ], define di ∈ {0, 1}m as the indicator vector of Ai : ( 1, j ∈ Ai , (di )j := 0, j ∈ / Ai . • Let T := {e1 , . . . , em } ⊆ Rm , where ej is the j-th canonical basis vector. This reduction is computable in polynomial time, and all coordinates of di and T are in {0, 1}. Now fix any S ⊆ [N ]. For any s = ej ∈ T , max ⟨di , ej ⟩ = max(di )j . i∈S0
Since each (di )j ∈ {0, 1} and d0 = 0, we have ( 1, max(di )j = i∈S0 0,
i∈S0
if there exists i ∈ S such that j ∈ Ai , otherwise.
Therefore, X
s∈T
Dividing by |T | = m gives
max ⟨di , s⟩ = i∈S0
m X j=1
(
1 j∈
F (S; T ) =
[
Ai
i∈S
)
=
[
Ai .
i∈S
1 [ Ai . m i∈S
Thus, maximizing F (S; T ) subject to |S| ≤ B is exactly equivalent (up to the constant factor 1/m) to solving the Max-Coverage instance. Since Max-Coverage is NP-hard, the directional coverage design problem is NP-hard as well. D.7
PROOF OF THEOREM 4.4
Proof. We use the same reduction from Max-Coverage as in the proof of Theorem 4.3. Let cov(S) :=
[
Ai
i∈S
denote the Max-Coverage objective value. For the constructed instance of (Pcov ), we proved that for every S ⊆ [N ], F (S; T ) =
1 cov(S). m
Hence the reduction preserves approximation ratios exactly: for any feasible S and any optimal solution S ⋆ , F (S; T ) cov(S) = . F (S ⋆ ; T ) cov(S ⋆ ) Suppose, for contradiction, that there exists a polynomial-time algorithm for (Pcov ) achieving approximation factor (1 − 1/e + ε) for some ε > 0. Applying it to the reduced instance and using the identity above would produce, in polynomial time, a solution S to Max-Coverage such that cov(S) ≥ (1 − 1/e + ε) cov(S ⋆ ). This contradicts the classical hardness-of-approximation barrier for Max-Coverage: for every ε > 0, no polynomial-time algorithm can achieve an approximation factor of 1 − 1/e + ε unless P = N P (see, e.g., Feige [1998]). Therefore, no polynomial-time algorithm can approximate (Pcov ) within a factor strictly better than 1 − 1/e unless P = NP. D.8
PROOF OF THEOREM 4.5
Proof. By Proposition 4.1, the set function F (·; T ) is monotone and submodular. Also, since d0 = 0 and S0 = {0} when S = ∅, we have 1 X F (∅; T ) = max ⟨di , s⟩ = 0. |T | i∈{0} s∈T
Therefore, the classical Nemhauser–Wolsey–Fisher theorem for monotone submodular maximization under a cardinality constraint implies that the greedy algorithm returns a set Sgreedy with F (Sgreedy ; T ) ≥ (1 − 1/e) max F (S; T ). |S|≤B
D.9
PROOF OF COROLLARY 4.6
Proof. Immediate from Theorem 4.4 and Theorem 4.5.
E
AVERAGE-TO-WORST BRIDGE ON THE FINITE PROBE SET
This section formalizes a sufficient condition under which improving the surrogate objective F (S; T ) also reduces the worst-case deficit maxs∈T ∆S (s) on the same probe set. Recall the notation from Appendix C.3. For any index set A ⊆ [N ]0 , define MA (s) := max⟨di , s⟩,
∆S (s) := M[N ]0 (s) − MS0 (s).
i∈A
For a fixed nonempty finite set T ⊂ Rp and a subset S ⊆ [N ], define the average deficit X ¯ S (T ) := 1 ∆ ∆S (s). |T | s∈T
Using the definition of F (·; T ), the surrogate gap satisfies the exact identity ¯ S (T ). F ([N ]; T ) − F (S; T ) = ∆ To convert this average quantity into a worst-case bound, define the local occupancy of the probe set under dD : µη (T ) := min |{t ∈ T : dD (s, t) ≤ η}| , s∈T
η ≥ 0.
Since T ̸= ∅ and dD (s, s) = 0, we have µη (T ) ≥ 1 for all η ≥ 0. Proposition E.1 (Average-to-worst bridge on T ). Let T ⊂ Rp be nonempty and finite. Then, for any S ⊆ [N ] and any η ≥ 0, |T | ¯ |T | max ∆S (s) ≤ ∆S (T ) + 2η = F ([N ]; T ) − F (S; T ) + 2η. s∈T µη (T ) µη (T )
Equivalently,
max ∆S (s) ≤ inf s∈T
η≥0
|T | ¯ ∆S (T ) + 2η . µη (T )
Proof. Appendix C.3 shows that, for any index set A ⊆ [N ]0 , the map MA (·) is 1-Lipschitz with respect to dD : |MA (s) − MA (s′ )| ≤ dD (s, s′ ). Therefore, since ∆S = M[N ]0 − MS0 , |∆S (s) − ∆S (s′ )| ≤ |M[N ]0 (s) − M[N ]0 (s′ )| + |MS0 (s) − MS0 (s′ )| ≤ 2 dD (s, s′ ). Hence ∆S (·) is 2-Lipschitz in dD . Let s⋆ ∈ arg maxs∈T ∆S (s) and define the dD -ball on the probe set Nη (s⋆ ) := {t ∈ T : dD (t, s⋆ ) ≤ η}. For any t ∈ Nη (s⋆ ), the 2-Lipschitz property gives ∆S (t) ≥ ∆S (s⋆ ) − 2η. Summing over Nη (s⋆ ) and using nonnegativity of ∆S (since S0 ⊆ [N ]0 implies M[N ]0 ≥ MS0 pointwise), ¯ S (T ) = |T | ∆
X t∈T
∆S (t) ≥
X
t∈Nη (s⋆ )
∆S (t) ≥ |Nη (s⋆ )| ∆S (s⋆ ) − 2η .
By definition of µη (T ), |Nη (s⋆ )| ≥ µη (T ), so
¯ S (T ) ≥ µη (T ) max ∆S (s) − 2η . |T | ∆ s∈T
Rearranging yields max ∆S (s) ≤ s∈T
|T | ¯ ∆S (T ) + 2η. µη (T )
¯ S (T ) with the surrogate gap: Finally, identify ∆ X ¯ S (T ) = 1 ∆ M[N ]0 (s) − MS0 (s) = F ([N ]; T ) − F (S; T ). |T | s∈T
This proves the first display. The infimum form follows immediately by minimizing the right-hand side over η ≥ 0. Corollary E.2 (Robust value-gap bound through the surrogate gap). Under the assumptions of Theorem 3.1, let T be an ε-net of q(X) in dD . Then, for any S ⊆ [N ] and any η ≥ 0, |T | min Φ[N ](x) − min ΦS (x) ≤ r F ([N ]; T ) − F (S; T ) + 2η + 2ε . x x µη (T )
Equivalently,
min Φ[N ](x) − min ΦS (x) ≤ r x
x
Proof. Theorem 3.1 gives
inf
η≥0
|T | F ([N ]; T ) − F (S; T ) + 2η µη (T )
+ 2ε .
min Φ[N ](x) − min ΦS (x) ≤ r max ∆S (s) + 2ε . x
x
s∈T
Apply Proposition E.1 to bound maxs∈T ∆S (s) and substitute.
Practical interpretation. The factor |T |/µη (T ) measures how densely the probe set covers itself under dD at resolution η. When T is well distributed in the relevant directions, this factor is moderate, and improving the surrogate objective F (S; T ) reduces the worst-case certificate term on T , up to the additive resolution term 2η. Conversely, if T is highly nonuniform (small local occupancy near some directions), then average coverage can be less informative about the worst-case deficit; the bound makes this dependence explicit.
F
DIRECTIONAL RELEVANCE IN THE ROBUST LP TEMPLATE
We first recall a minimal linear-programming instantiation of the robust template, and then use LP duality to isolate the directions of uncertainty that are value-relevant for the full directional model. This yields a dual-based notion of relevance that will serve as a structural benchmark for any restricted family US (r). Minimal LP template.
Let X = {x : Ax ≤ b} and f (x, u) = c(u)⊤ x with c(u) = c0 + M u. Then ⊤ ΦS (x) = c⊤ 0 x + r max di , M x , i∈S0
and minx ΦS (x) is an LP after introducing a variable to linearize the maximum. Pessimization over [N ] reduces to evaluating i⋆ ∈ arg max di , M ⊤ x . i∈[N ]0
F.1
SETUP AND NOTATION
Assume a compact polyhedral feasible region X := {x ∈ Rn : Ax ≤ b}, and an affine objective coefficient map c(u) = c0 + M u, ⊤
so that the nominal objective is f (x, u) = c(u) x. The full directional robust objective is ⊤ Φ[N ] (x) = c⊤ 0 x + r max di , M x . i∈[N ]0
F.2
ROBUST LP TEMPLATE AND DUAL
We adopt the following standing setup. Assumption F.1 (Robust LP template). Let X := {x ∈ Rn : Ax ≤ b} be a nonempty, bounded polyhedron, with A ∈ Rm×n and b ∈ Rm . The uncertain cost is c0 ∈ Rn , M ∈ Rn×p ,
c(u) := c0 + M u,
p and the directional dictionary is D = {di }N i=1 ⊂ R , with d0 := 0 and [N ]0 := {0, 1, . . . , N }. For S ⊆ [N ] and r > 0, n o P P US (r) := u = i∈S αi di : αi ≥ 0, i∈S αi ≤ r .
The full model corresponds to S = [N ]. The robust value of the full model is
⋆ z[N ] := min
sup
x∈X u∈U
(c0 + M u)⊤ x.
[N ] (r)
Using the support function of U[N ] (r) and introducing an epigraph variable t ∈ R we obtain the equivalent LP (P[N ])
⋆ ⊤ z[N ] = min c0 x + rt x,t
s.t.
(10)
Ax ≤ b, ⊤
(M di ) x ≤ t,
∀i ∈ [N ]0 .
We now write its dual in a form that exposes the role of the dictionary. Proposition F.2 (Dual of the full robust LP). Under Assumption F.1, the dual of (P[N ]) is (D[N ])
− b⊤ λ
⋆ z[N ] = max λ,µ
s.t.
A⊤ λ = − c 0 − M X µi = r,
P
µ d , i i i∈[N ]0
(11)
i∈[N ]0
λ ≥ 0,
µi ≥ 0, ∀i ∈ [N ]0 .
⋆ Strong duality holds: (P[N ]) and (D[N ]) have the same finite optimal value z[N ]. ⊤ Proof. Assign dual variables λ ∈ Rm + to Ax ≤ b and µi ≥ 0 to (M di ) x − t ≤ 0 for i ∈ [N ]0 . The Lagrangian of (10) is
L(x, t; λ, µ) = c0 + A⊤ λ + M
P
i∈[N ]0 µi di
⊤
x+ r−
P
i∈[N ]0 µi
t − b⊤ λ.
For inf x,t L(x, t; λ, µ) to be finite we need both coefficients of x and t to vanish. This yields the two equalities in (11); under them, L(x, t; λ, µ) ≡ −b⊤ λ. Maximizing over (λ, µ) subject to feasibility gives (D[N ]). Strong duality follows from standard LP duality under boundedness and feasibility of X. F.3
VALUE-RELEVANT DIRECTIONS AND THE RELEVANT FACE
Optimal dual solutions reveal which dictionary atoms are actually used in the worst-case cost at the robust optimum. Definition F.3 (Value-relevant indices and face). Let (x⋆ , t⋆ ) and (λ⋆ , µ⋆ ) be optimal solutions of (P[N ]) and (D[N ]), respectively. Define the set of value-relevant indices Irel := {i ∈ [N ] : µ⋆i > 0},
and the corresponding relevant face Crel := conv {di : i ∈ Irel } ∪ {0} ⊆ conv {di : i ∈ [N ]} ∪ {0} .
We also define the associated worst-case direction X
u⋆ :=
i∈[N ]0
µ⋆i di ∈ U[N ] (r),
v ⋆ :=
1 ⋆ u ∈ Crel . r
By complementary slackness, every index i ∈ Irel corresponds to a binding constraint (M di )⊤ x⋆ = t⋆ in (P[N ]). The vector u⋆ is a worst-case perturbation at x⋆ , and v ⋆ lies in an exposed face of conv(D ∪ {0}) determined by M ⊤ x⋆ . F.4
DIRECTIONAL SUFFICIENCY VIA THE DUAL
For S ⊆ [N ], define the restricted uncertainty set US (r) as in Assumption F.1, and denote by zS⋆ the corresponding robust value: zS⋆ := min sup (c0 + M u)⊤ x. x∈X u∈US (r)
The following theorem gives a dual-based notion of directional sufficiency for the full robust value. Theorem F.4 (Global directional sufficiency via the dual). Adopt Assumption F.1 and let (λ⋆ , µ⋆ ) be any optimal solution of (D[N ]), with associated value-relevant set Irel and face Crel = conv({di : i ∈ Irel } ∪ {0}). Let S ⊆ [N ] and suppose that Crel ⊆ conv{di : i ∈ S0 }. (12) Then the robust values of the full and restricted models coincide: ⋆ zS⋆ = z[N ].
P Proof. Let u⋆ := i∈[N ]0 µ⋆i di ∈ U[N ] (r) and v ⋆ := u⋆ /r ∈ Crel . By (12), there exist coefficients {αj }j∈S0 with αj ≥ 0 P and j∈S0 αj = 1 such that v⋆ =
X
αj dj ,
u⋆ = rv ⋆ =
hence
j∈S0
Define coefficients µ ej := rαj for j ∈ S0 . Then µ ej ≥ 0 and c0 + M
X
j∈S0
X
(rαj )dj .
j∈S0
P
ej = r, and j∈S0 µ
µ ej dj = c0 + M u⋆ = c0 + M
X
i∈[N ]0
µ⋆i di = −A⊤ λ⋆ ,
where the last equality uses feasibility of (λ⋆ , µ⋆ ) in (D[N ]). Thus (λ⋆ , µ e) is feasible for the dual of the restricted model ⋆ (D[S]), with objective value −b⊤ λ⋆ = z[N . By strong duality for (P[S])–(D[S]), ] ⋆ zS⋆ = max{−b⊤ λ : (λ, µ) feasible in (D[S])} ≥ −b⊤ λ⋆ = z[N ].
⋆ On the other hand, US (r) ⊆ U[N ] (r) implies monotonicity of the robust value in the uncertainty set, whence zS⋆ ≤ z[N ]. ⋆ ⋆ Combining the two inequalities yields zS = z[N ] .
F.5
INSTANCE-WISE NO-FREE-LUNCH FOR INSUFFICIENT SUBSETS
We now show that if a subset S fails to represent the relevant convex geometry of the dictionary, then there is no uniform guarantee relating the restricted and full robust values: one can construct instances for which the value gap is arbitrarily large.
p Theorem F.5 (Instance-wise no-free-lunch for insufficient subsets). Let D = {di }N i=1 ⊂ R be a finite dictionary and let S ⊂ [N ] be such that conv{di : i ∈ S} ⊊ conv{di : i ∈ [N ]}.
Then there exist a dimension n ∈ N, a nonempty bounded polyhedron X ⊂ Rn and data (A, b, c0 , M, r) for the robust LP template of Assumption F.1 (with this X and D) such that, for the corresponding full and restricted robust values ⋆ ⋆ z[N ] and zS , the following holds: for every K > 0 one can choose (A, b, c0 , M, r) with ⋆ ⋆ z[N ] − zS ≥ K.
In particular, the family of restricted models based on US (r) cannot provide a uniform approximation of the full directional model across all robust LP instances built on the same dictionary D. Proof. Since conv{di : i ∈ S} ⊊ conv{di : i ∈ [N ]}, the polytope conv{di : i ∈ [N ]} has at least one extreme point that does not belong to conv{di : i ∈ S}. Let di0 be such an extreme point. By the separating hyperplane theorem, there exists q ∈ Rp such that ⟨di0 , q⟩ > max ⟨y, q⟩ = max⟨dj , q⟩. j∈S
y∈conv{di :i∈S}
In particular, ∆ := max ⟨di , q⟩ − max⟨dj , q⟩ > 0. j∈S
i∈[N ]
We construct an instance in dimension n = 1. Let X := {x ∈ R : x = 1}, which is a nonempty bounded polyhedron (it can be written as {x : x ≤ 1, −x ≤ −1}). Take c0 := 0 ∈ R and define M ∈ R1×p by M := q ⊤ . For any u ∈ Rp and x ∈ X, (c0 + M u)⊤ x = (M u) x = q ⊤ u.
For radius r > 0, the robust values of the full and restricted models are ⋆ z[N ] =
sup u∈U[N ] (r)
q ⊤ u = r max ⟨di , q⟩, i∈[N ]0
zS⋆ =
sup q ⊤ u = r max⟨dj , q⟩,
u∈US (r)
j∈S0
where S0 := S ∪ {0} and [N ]0 := {0, 1, . . . , N }. By definition of ∆ and the inclusion of 0 in both index sets, we have max ⟨di , q⟩ − max⟨dj , q⟩ ≥ max ⟨di , q⟩ − max⟨dj , q⟩ = ∆ > 0. j∈S0
i∈[N ]0
Therefore ⋆ ⋆ z[N ] − zS = r
j∈S
i∈[N ]
max ⟨di , q⟩ − max⟨dj , q⟩ ≥ r ∆.
i∈[N ]0
j∈S0
⋆ ⋆ Given any prescribed K > 0, choosing r := K/∆ yields z[N ] − zS ≥ K, as claimed.
G
GREEDY WITH INEXACT ORACLE/SELECTION AND VALUE CERTIFICATE
In practice, the marginal gains of F (·; T ) (see (9)) are computed with error and the selection rule can be suboptimal. We model this per iteration. Assumption G.1 (Per-iteration inexact selection). At iteration t, let ∆Ftmax be the best possible marginal gain of F (·; T ) among all indices i ∈ [N ] \ St−1 , that is, ∆Ftmax := max F (St−1 ∪ {i}; T ) − F (St−1 ; T ) . i∈[N ]\St−1
We assume the chosen index it satisfies
∆Ft (chosen) ≥ (1 − ρ) ∆Ftmax − εt , with ρ ∈ [0, 1) (multiplicative suboptimality) and εt ≥ 0 (additive error).
Theorem G.2 (Inexact greedy guarantee for F ). Under submodularity and monotonicity of F (·; T ) and Assumption G.1, after B steps, B B B−t X 1−ρ ⋆ F (Saprx ; T ) ≥ 1 − 1 − 1−ρ F (S εt , ; T ) − 1 − B B t=1
⋆
⋆
where S maximizes F (·; T ) with |S | ≤ B. In particular,
1 − 1−ρ B
B
≤ e−(1−ρ)
⇒
B X 1−ρ F (Saprx ; T ) ≥ 1 − e−(1−ρ) F (S ⋆ ; T ) − e− B (B−t) εt . t=1
Proof. Let St be the subset selected after t iterations, with S0 = ∅, and let Gt := F (S ⋆ ; T ) − F (St ; T ). We write F (·) for F (·; T ) to simplify notation. By monotonicity and submodularity, the standard greedy lower bound gives ∆Ftmax ≥
1 1 F (S ⋆ ) − F (St−1 ) = Gt−1 . B B
(Indeed, adding the elements of S ⋆ \ St−1 one by one and using submodularity yields F (S ⋆ ) − F (St−1 ) ≤ B ∆Ftmax since |S ⋆ | ≤ B.) By Assumption G.1, F (St ) − F (St−1 ) = ∆Ft (chosen) ≥ (1 − ρ) ∆Ftmax − εt ≥ Rearranging,
1−ρ Gt−1 − εt . B
1 − ρ Gt = F (S ⋆ ) − F (St ) ≤ 1 − Gt−1 + εt . B
Set a := 1 −
1−ρ ∈ [0, 1). B
Then the recurrence is Gt ≤ a Gt−1 + εt . Unrolling for t = 1, . . . , B gives GB ≤ aB G0 +
B X
aB−t εt .
t=1
Since S0 = ∅ and F (∅; T ) = 0 (because d0 = 0 is included), we have G0 = F (S ⋆ ; T ) − F (∅; T ) = F (S ⋆ ; T ). Therefore, ⋆
B
⋆
F (SB ; T ) = F (S ; T ) − GB ≥ (1 − a )F (S ; T ) − Since Saprx = SB , this proves the first claim.
B X
aB−t εt .
t=1
For the exponential form, use (1 − x) ≤ e−x with x = (1 − ρ)/B: 1 − ρ B aB = 1 − ≤ e−(1−ρ) , B
Substituting these bounds yields the second inequality.
1−ρ
aB−t ≤ e− B (B−t) .
Remark G.3 (Mapping oracle errors to (ρ, εt )). If at iteration t the marginal gains are evaluated with a uniform additive error δt both for F (St−1 ∪ {i}) and for F (St−1 ), then ρ = 0 and εt ≤ 2δt (the gain is a difference of two quantities, each with error ≤ δt ). If moreover only a multiplicative factor (1 − ρ̃) with respect to the best gain is guaranteed, one may take ρ = ρ̃.
Robust value certificate with inexact selection. Combining the pointwise value-gap identity (5)–(6) with a finite family T (Section 3.1), we obtain the deterministic certificate min Φ[N ] (x) − min ΦSaprx (x) ≤ r max ∆Saprx (s) + 2ε , (13) x
x
s∈T
where ε is the grid granularity over q(X) (Theorem 3.1). The right-hand side is computable at run time. Certified stopping rule.
Fix a threshold τ > 0; stop when max ∆S (s) ≤ s∈T
τ 2r
and
ε ≤
τ , 4r
and report the certificate min Φ[N ] − min ΦS ≤ τ .
H
EXPERIMENTAL DETAILS
This appendix provides implementation details for the experiments in Sec. 5, covering out-of-sample calibration, frozen feature classification, and scaling and runtime metrics. Hardware and implementation details. All methods were implemented in Python 3.10.12 and experiments ran on Ubuntu Linux with an Intel® Xeon® Gold 6230R processor (104 logical cores, 2.10 GHz) and 187 GiB of memory. Wall clock runtime is reported. H.1
OUT-OF-SAMPLE CALIBRATION USAGE AND CONSERVATISM
Radius calibration applies to the synthetic geometric validation experiment. For a selected subset S, a radius rb(S) is estimated from a calibration set, reporting the guarantee of Theorem 3.3. In the frozen feature classification experiment, radius is not calibrated; the reported metric is the certified accuracy induced by the atomic model and the dictionary. Calibration conservatism and out-of-sample feasibility. This subsection reports a calibration ablation for the synthetic pipeline. The analysis compares DKW union calibration against split calibration on a held out test split, detailing sensitivity to the target violation level α and confidence parameter δ. Results are computed from calibration_ablation.csv, storing one row per (B, α, δ, method) configuration. Configurations include budgets B ∈ {9, 19, 29}, target levels α ∈ {0.01, 0.03, 0.05, 0.1}, confidence levels δ ∈ {10−5 , 10−4 , 10−3 }, and calibration methods {DKW union, Split}. Table 5 summarizes the ablation by calibration method and confidence parameter. DKW union calibration produces higher d − α) across tested δ. Split calibration yields correction terms and calibrated radii, with negative mean violation gaps (viol lower radii and positive mean violation gaps.
For DKW union, the mean correction term changes from 0.2316 at δ = 10−3 to 0.2367 at δ = 10−5 , and the mean violation gap remains negative (-0.0082 to -0.0086). For split calibration, the mean correction term changes from 0.0616 to 0.0781, while the mean violation gap remains positive (0.0048 to 0.0037). Table 6 summarizes these quantities by budget after averaging over tested (α, δ) pairs. DKW union radius increases with budget because the union correction grows with combinatorial family size, while split correction remains constant. Figure 7 reports correction magnitude at the default confidence level, and Figure 8 reports the ablation over (α, δ) for both calibration methods. The left panel plots observed out-of-sample violation against the target level at default confidence. The right panel plots the violation gap as a function of the confidence parameter at fixed α = 0.05.
Table 5: Calibration ablation summary by method and confidence parameter. Gap is observed violation minus target level. Method DKW union DKW union DKW union Split Split Split
δ 10−5 10−4 10−3 10−5 10−4 10−3
Mean corr. 0.2367 0.2342 0.2316 0.0781 0.0704 0.0616
Mean radius 4.4114 4.4089 4.4064 4.2529 4.2451 4.2364
Mean viol. 0.0389 0.0391 0.0393 0.0512 0.0519 0.0524
Mean gap -0.0086 -0.0084 -0.0082 0.0037 0.0044 0.0048
Max gap 0.0000 0.0000 0.0000 0.0088 0.0100 0.0106
Min gap -0.0254 -0.0250 -0.0248 0.0008 0.0016 0.0026
Table 6: Calibration ablation summary by budget and calibration method, averaged over (α, δ) settings. B 9 9 19 19 29 29
Method DKW union Split DKW union Split DKW union Split
Mean corr. 0.1809 0.0700 0.2397 0.0700 0.2818 0.0700
Mean radius 4.3557 4.2448 4.4144 4.2448 4.4566 4.2448
Mean viol. 0.0429 0.0518 0.0385 0.0518 0.0360 0.0518
Mean gap -0.0046 0.0043 -0.0090 0.0043 -0.0115 0.0043
Table 7 reports configurations at α = 0.05 for tested budgets and confidence levels. Metrics include raw calibration quantile, correction term, calibrated radius, observed violation, and violation gap. The pairwise correction ratio between DKW union and split calibration, computed at matched (B, α, δ) settings, has mean 3.3715 and maximum 4.5388. The radius increase induced by DKW union averages 0.1641, while the change in violation d − α) averages -0.0127. gap (viol DKW union calibration provides feasibility control with higher correction terms and calibrated radii, while split calibration yields lower radii but can exceed the target violation level on the held out test split. H.2
SYNTHETIC GEOMETRIC VALIDATION
A synthetic two dimensional dictionary with N = 2000 atoms and budgets B ∈ {2, 4, 8, 16, 32} is utilized. Support approximation is evaluated along xfixed = (1, 0). A calibration set of size mcal = 1000 is employed with (α, δ) = (0.05, 10−5 ). The dictionary is generated once and reused. It mixes structured directions, isotropic noise, and decoy directions orthogonal to xfixed . For any subset S, the following is reported: zS (r) =
sup ⟨u, xfixed ⟩ = r max 0, max⟨di , xfixed ⟩ , i∈S
u∈US (r)
and compared to z[N ] (r). An ellipsoidal baseline fitted to the calibration sample is included. H.2.1
Surrogate versus certificate alignment in the synthetic validation
This subsection quantifies the relationship between the surrogate selection objective and the reported worst deficit certificate proxy in the synthetic geometric validation. The selection step uses the average coverage objective F (S; Teval ), while the reporting includes the worst deficit proxy G(S; Teval ) := reval max ∆S (s). s∈Teval
A direct empirical comparison between these quantities clarifies when improvements in the surrogate objective align with improvements in the certificate proxy.
Calibration Correction Magnitude
0.30
Union correction Split correction
Correction term
0.25 0.20 0.15 0.10 3
5
7
9
11
13
15
17 19 Budget B
21
23
25
27
29
31
Figure 7: Calibration correction magnitude at the default confidence level. DKW union correction increases with budget; split correction is constant. Table 7: Calibration settings at fixed α = 0.05 for tested budgets and confidence levels. B 9 9 9 9 9 9 19 19 19 19 19 19 29 29 29 29 29 29
δ 10−5 10−5 10−4 10−4 10−3 10−3 10−5 10−5 10−4 10−4 10−3 10−3 10−5 10−5 10−4 10−4 10−3 10−3
Method DKW union Split DKW union Split DKW union Split DKW union Split DKW union Split DKW union Split DKW union Split DKW union Split DKW union Split
Quantile 3.9942 3.9942 3.9942 3.9942 3.9942 3.9942 3.9942 3.9942 3.9942 3.9942 3.9942 3.9942 3.9942 3.9942 3.9942 3.9942 3.9942 3.9942
Corr. 0.1841 0.0781 0.1810 0.0704 0.1778 0.0616 0.2421 0.0781 0.2397 0.0704 0.2373 0.0616 0.2839 0.0781 0.2819 0.0704 0.2798 0.0616
Radius 4.1783 4.0723 4.1752 4.0646 4.1720 4.0559 4.2363 4.0723 4.2339 4.0646 4.2315 4.0559 4.2781 4.0723 4.2761 4.0646 4.2740 4.0559
Viol. 0.0490 0.0588 0.0492 0.0600 0.0492 0.0606 0.0432 0.0588 0.0438 0.0600 0.0438 0.0606 0.0390 0.0588 0.0392 0.0600 0.0396 0.0606
Gap -0.0010 0.0088 -0.0008 0.0100 -0.0008 0.0106 -0.0068 0.0088 -0.0062 0.0100 -0.0062 0.0106 -0.0110 0.0088 -0.0108 0.0100 -0.0104 0.0106
For each method and budget, the following normalized metrics are evaluated: Fratio (S) :=
F (S; Teval ) , F ([N ]; Teval )
Gratio (S) :=
G(S; Teval ) . G(∅; Teval )
The correlation is computed between Fratio and −Gratio , so larger values on both axes correspond to better performance. The statistics in this subsection use all available budgets exported by the synthetic experiment. Table 8 reports the aggregate statistics. The Spearman correlation indicates a monotone alignment between the surrogate objective and the certificate proxy in this setup. The Greedy Coverage and Greedy MaxGap comparison shows divergence only at budgets B ∈ {1, 3, 4}. This localizes the mismatch to the micro budget regime. Figure 9 plots the normalized surrogate objective against the normalized certificate proxy across methods and budgets, together with a direct Greedy Coverage versus Greedy MaxGap difference diagnostic. The first panel shows a monotone trend. The second panel reports two normalized differences for each budget: GC GM ∆F := Fratio − Fratio ,
GC ∆Gscore := GGM ratio − Gratio ,
where positive ∆Gscore means Greedy Coverage achieves a smaller certificate proxy. A sign disagreement between ∆F and ∆Gscore indicates a surrogate versus certificate divergence.
Calibration Ablation: DKW-union vs Split and (alpha, delta) Sensitivity OOS violation vs (default )
0.08
0.010 0.005 Observed violation
Observed OOS violation
0.10
Violation gap vs (fixed = 0.05)
Union (B=9) Union (B=19) Union (B=29) Split (B=9) Split (B=19) Split (B=29) y=x
0.06 0.04
Union (B=9) Union (B=19) Union (B=29) Split (B=9) Split (B=19) Split (B=29)
0.000 0.005
0.02 0.010 0.02
0.04
0.06 Target
0.08
0.10
10 3
10 4 Confidence level parameter
10 5
Figure 8: Calibration ablation with (α, δ) sweeps. Left: observed out-of-sample violation versus target α at default confidence d − α) versus δ at fixed α = 0.05. level. Right: violation gap (viol Table 8: Summary of surrogate versus certificate alignment in the synthetic geometric validation. Quantity Number of analyzed points Pearson corr(Fratio , −Gratio ) Spearman corr(Fratio , −Gratio ) Budgets with GC versus GM divergence Divergence budgets Surrogate versus certificate across methods and budgets B=1
0.8
B=1
B=1
Divergence diagnosis: Greedy-Coverage vs Greedy-MaxGap
Greedy-Coverage Greedy-MaxGap MaxNorm TopAct
B=31
0.5
0.6 0.4 0.2
F (GC - GM) G score (GM - GC)
0.4 Difference (normalized)
Normalized certificate proxy G(S; Teval)/G0
1.0
Value 124 0.8554 0.9617 3 {1, 3, 4}
0.3 0.2 0.1 0.0 0.1
0.0
B=31
0.2
0.4 0.6 0.8 Normalized surrogate F(S; Teval)/Ffull
1.0
0.2 1 2 3 4 5 6 7 8 9 10111213141516171819202122232425262728293031 Budget B
Figure 9: Surrogate versus certificate analysis in the synthetic geometric validation. Left: normalized surrogate objective Fratio versus normalized certificate proxy Gratio across methods and budgets. Lower values of Gratio are better. Right: direct comparison between Greedy Coverage and Greedy MaxGap through ∆F and ∆Gscore as functions of the budget.
Table 9 reports representative budget values for the Greedy Coverage versus Greedy MaxGap comparison. Divergence is confined to the smallest budgets, while the two criteria align after that regime. Table 10 summarizes the start and end points of each method trajectory. The normalized trajectories support the same conclusion: the surrogate objective acts as a guide for the certificate proxy beyond the smallest budgets in this synthetic setup. In the synthetic geometric validation, the surrogate objective F and the certificate proxy G align well overall, with divergence concentrated in the micro budget regime. This supports using the submodular surrogate for selection while preserving the worst deficit metric as the reporting and diagnostic quantity.
Table 9: Representative Greedy Coverage versus Greedy MaxGap comparisons. Positive ∆F favors Greedy Coverage on the surrogate objective. Positive ∆Gscore favors Greedy Coverage on the certificate proxy. B 1 3 4 5 9 19 29
∆F 0.1803 0.4705 0.2620 0.2618 0.0396 0.0000 0.0000
∆Gscore −0.1918 −0.0017 −0.0390 0.4472 0.0857 0.0000 0.0000
GC Fratio 0.5193 0.9924 0.9962 0.9989 1.0000 1.0000 1.0000
GC Gratio 1.0000 0.7531 0.7531 0.2097 0.0000 0.0000 0.0000
GM Fratio 0.3390 0.5219 0.7342 0.7371 0.9604 1.0000 1.0000
GM Gratio 0.8082 0.7513 0.7140 0.6568 0.0857 0.0000 0.0000
Table 10: Method trajectory endpoints in normalized surrogate and certificate coordinates. Method Greedy Coverage Greedy MaxGap MaxNorm TopAct
H.3
Fratio (start → end) 0.5193 → 1.0000 0.3390 → 1.0000 0.1736 → 0.3737 0.5193 → 1.0000
Gratio (start → end) 1.0000 → 0.0000 0.8082 → 0.0000 0.8082 → 0.7514 1.0000 → 0.0000
OPERATIONALIZING THE ε TERM IN THEOREM 3.1
This section reports an empirical evaluation of the discretization term in Theorem 3.1, quantifying the approximation gap induced by replacing the direction set q(X) with a finite set T . Let dD (s, t) = max |⟨di , s − t⟩| i
and let Tprobe denote an independent probe pool of normalized directions. The empirical discretization error is defined as εb(T ) = max min dD (s, t). s∈Tprobe t∈T
This quantity is the empirical counterpart of the ε net radius in Theorem 3.1. In the synthetic two dimensional experiment, the same finite set T is used for selection and reporting, with |T | = 801, and the independent probe set has |Tprobe | = 4000. The estimate is: εb(T ) = 1.824282,
2b ε(T ) = 3.648563.
Empirical in dD vs net size epsilon-hat for fixed T used in experiment
2.5
probe
= smax min d (s, t) t T D T
2.4 2.3 2.2 2.1 2.0 1.9 1.8
0
100
200
300 400 500 Net size |T| (including xeval)
600
700
800
Figure 10: Empirical discretization error εb(T ) in the metric dD as a function of the net size |T |. The curve is computed from nested prefixes of the direction pool and an independent probe set Tprobe . The estimated curve decreases monotonically over the reported refinement path. Table 11 summarizes the statistics. The mean and the 95th percentile of the nearest net distance are small relative to the supremum εb(T ), indicating the worst case discretization term is driven by a small subset of probe directions.
Table 11: Summary of the empirical εb(T ) estimate in the synthetic two dimensional experiment. Quantity
Value
|T | used in selection and reporting |Tprobe | Number of metric atoms used for dD εb(T ) 2b ε(T ) Mean nearest net distance on Tprobe 95th percentile nearest net distance on Tprobe
801 4000 8 1.824282 3.648563 0.013876 0.027180
Table 12: Empirical εb(T ) along the net refinement path. |T |
εb(T )
26 51 101 201 401 801
2.551961 2.530695 2.517097 2.433706 1.876200 1.824282
Table 12 reports the refinement path. The empirical estimate decreases from 2.551961 to 1.824282 as |T | increases from 26 to 801, representing a reduction of 28.51%. Theorem 3.1 bounds the robust value gap through the term max ∆S (t) + 2ε. t∈T
Using the empirical estimate εb(T ), this section reports the practical decomposition max ∆S (t) + 2b ε(T ). t∈T
Figure 11 shows this decomposition for Greedy Coverage and Greedy MaxGap. Thm 3.1 Proxy Bound Decomposition on Fixed T Greedy-Coverage: max (t) t T S Greedy-MaxGap: max (t) t T S Greedy-Coverage: max + 2 Greedy-MaxGap: max + 2 Constant term 2
6
Bound term (with r = 1)
5 4 3 2 1 0 3
5
7
9
11
13
15
17 19 Budget B
21
23
25
27
29
31
Figure 11: Empirical decomposition of the Theorem 3.1 bound term on the finite set T . The curves show maxt∈T ∆S (t) and maxt∈T ∆S (t) + 2b ε(T ) for Greedy Coverage and Greedy MaxGap. The horizontal line corresponds to the constant discretization contribution 2b ε(T ). The decomposition reveals two regimes. For small budgets, the reduction in the bound results from the decrease in maxt∈T ∆S (t). For moderate budgets, the alignment deficit becomes small, and the constant term 2b ε(T ) dominates. In this
range, increasing the atom budget B has minimal effect on the certificate, and the primary method to tighten the bound is the refinement of the direction set T . For reference, Greedy Coverage reaches maxt∈T ∆S (t) = 0 at B = 9 in this experiment, while Greedy MaxGap reaches maxt∈T ∆S (t) = 0 at B = 17. Table 13: Representative values of the practical Theorem 3.1 decomposition for Greedy Coverage and Greedy MaxGap. B 3 5 9 19 29
Greedy Coverage
Greedy MaxGap
maxt∈T ∆S (t)
+ 2b ε(T )
maxt∈T ∆S (t)
+ 2b ε(T )
2.438163 0.678860 0.000000 0.000000 0.000000
6.086726 4.327424 3.648563 3.648563 3.648563
2.432507 2.126637 0.277614 0.000000 0.000000
6.081070 5.775201 3.926178 3.648563 3.648563
2b ε(T ) 3.648563 3.648563 3.648563 3.648563 3.648563
Although Greedy Coverage optimizes an average coverage objective, it matches or improves the worst case deficit maxt∈T ∆S (t) at several budgets shown in Table 13. The empirical estimate εb(T ) makes the discretization term in Theorem 3.1 computable. The reported decomposition shows atom selection controls the alignment deficit at small budgets, while net refinement controls the certificate once maxt∈T ∆S (t) is small. This provides a diagnostic for deciding whether to increase B or to enrich the direction set T . H.4
FROZEN FEATURE CIFAR CLASSIFICATION
A pretrained ResNet 18 backbone is used to extract frozen features. Tasks are binary, defined by two classes from CIFAR 10 or CIFAR 100, with labels mapped to {−1, +1}. The training features are split into disjoint parts with proportions [0.5, 0.2, 0.15, 0.15], used for classifier training, dictionary mining, selection directions, and reporting directions. A linear classifier is trained with Adam and fixed hyperparameters. A dictionary is mined in feature space using a projected gradient attack in ℓ2 with radius ε. Normalized perturbation directions are stored, and certified accuracy CertAcc(ε) alongside projected gradient robust accuracy are evaluated. d Certified accuracy. Let w ∈ Rd be the weight vector of the linear classifier, and let D = {di }N i=1 ⊆ R be the directional dictionary in feature space. Define penD (w) := max ⟨di , w⟩ . i∈[N ]
For ε > 0, define n
CertAccD (ε) :=
1X 1{yj ⟨w, xj ⟩ > ε penD (w)} , n j=1
where (xj , yj ) are test examples in feature space and yj ∈ {−1, +1}. For a selected subset S ⊆ [N ], the reported metric is CertAccS (ε), obtained by replacing penD with penS (w) = maxi∈S |⟨di , w⟩|. H.5
FULL INSTANCE CONTEXT FOR BUDGET EFFICIENCY AND RELIABILITY ANALYSIS
Section 5.3 reports onset budget B ⋆ and budget-wise success rates on the subset of instances that are robust feasible under the full dictionary baseline, with zero violations. This conditioning isolates budget efficiency from baseline infeasibility. Across all generated seeds (N = 100), the full dictionary baseline is robust feasible on 64 seeds (64.0%) and infeasible on 36 seeds (36.0%). Table 14 summarizes policy-level certification counts over all 100 seeds on the same budget grid used in Section 5.3, making the screening step explicit.
Table 14: Policy-level certification summary over all generated instances (N = 100) for the experiment in Section 5.3. Full feasible and Full infeasible refer to feasibility under the full dictionary baseline. Policy
Full feasible
Full infeasible
Total certified
Not certified
greedy-maxgap 58/64 (90.6%) greedy-coverage 55/64 (85.9%) max-gamma 53/64 (82.8%)
3/36 (8.3%) 3/36 (8.3%) 3/36 (8.3%)
61/100 (61.0%) 39/100 (39.0%) 58/100 (58.0%) 42/100 (42.0%) 56/100 (56.0%) 44/100 (44.0%)
The N = 64 subset in Section 5.3 is the relevant population for onset budget and budget-wise efficiency comparisons because those metrics are meaningful only when the full dictionary baseline is robust feasible. Table 14 complements that analysis by reporting certification outcomes on the full instance pool. Certification on full-baseline infeasible seeds does not imply feasibility of the full dictionary baseline. It means that a policy achieves zero violations for that seed at some evaluated budget in its policy-specific sweep, while full-baseline feasibility is defined with respect to the full dictionary baseline.