We consider minimising a spectral risk objective, the expected cost plus a weighted conditional value-at-risk, when the distribution of the uncertain parameters depends on the decision and can only be sampled through a stochastic simulator under a fixed budget of draws. We propose adaptive conditional residual sampling (ACRS). It takes one simulator draw at each point of a space-filling design, fits a heteroscedastic regression model of the decision-dependent distribution and reuses the standardised residual vectors as scenarios to construct a deterministic surrogate. ACRS searches this surrogate for several local optima, adds draws around the most promising ones, ranks the candidates on the simulator with common random numbers and finishes with sample-path local refinement using tail importance sampling. We show that the optimality gap of the surrogate minimiser is bounded by the Wasserstein error of the scenario distribution and that the refinement estimator is consistent. In the experiments, all methods share the budget accounting, the design sampler and the local refinement routine, and solutions are scored by normalised regret against reference optima. On 60 random instances of an analytic family with a closed-form objective, ACRS attains a mean regret of 11.8% against 22.3-42.3% for Bayesian optimisation, cross-entropy, kernel-density, stochastic-gradient and refinement-only baselines; its lead is largest at small budgets and, relative to the kernel-density method, tends to grow with the dimension. ACRS also has the lowest mean regret on two six-dimensional benchmarks and three development problems, and performs comparably to pure local refinement on three held-out problems frozen before testing.
Figures & tables
Figure 1: Schematic of ACRS. Phases 1–4 form the global phase; phase 5 is the local refinement routine, which all methods in the experiments use whenever enough budget remains. Budget shares refer to the total budget B of simulator draws; the reranking budget is spent only if the surrogate has more than one distinct candidate. Every simulator draw is debited from one counter with hard cap B ; on exhaustion the incumbent is returned
Family
d
m
Units
B (k)
Reps
Final evaluation
Analytic family
2–8
3
60 instances
2, 5 or 10
4
exact
DGP1, DGP2 a
6
5
18 settings
5, 10, 30
30
20,000 draws
E1–E3 (development)
3–5
2–5
9 settings
2, 5, 10
20
100,000 draws
E4–E6 (held-out)
3–5
3–5
9 settings
2, 5, 10
20
100,000 draws
Table 1: Benchmark families. d : decision dimension; m : dimension of W ; B : simulation budget. Each analytic instance has one budget, drawn at random. Final evaluation is exact or uses a large sample of common random numbers shared by all methods within a replication a a footnotetext: Each with λ∈{0.5,0.7,0.9} .
Adam with common-random-number central differences
≈ 85%
best checkpoint overall and of each chain
Refine-only
none
0%
3 random feasible points
Table 2: Methods compared. All methods use the same design sampler and, whenever enough budget remains, the same local refinement (Section 4.5 ), which receives the listed starting points and uses the remaining budget
Opponent
Mean regret
ACRS better / tie / worse
p
Analytic family, 60 instances; ACRS mean regret 11.8
GP-BO
29.4
48
7
5
< 0.001
CEM
22.3
40
14
6
< 0.001
KDE-SO
26.1
38
17
5
< 0.001
SGD-CVaR
42.3
56
2
2
< 0.001
Refine-only
22.9
39
12
9
< 0.001
Table 3: Head-to-head comparison of ACRS with each competitor, by family. Units are instances (analytic family) or settings (other families), summarised by their mean normalised regret. Better/tie/worse count units on which ACRS has lower, equal (within 0.5) or higher mean regret; p is a two-sided paired Wilcoxon signed-rank test on unit means, Holm-adjusted over the five competitors within each family (unadjusted for the best competitor per unit) a a footnotetext: For each unit, the competitor with the lowest mean regret on that unit, chosen after the fact.
Figure 2: Analytic family: mean normalised regret by (a) budget (thousands of simulator draws) and (b) decision dimension, with 95% bootstrap intervals over instances (60 instances, 4 replications each). Methods are distinguished by marker shape and line type
n
ACRS
GP-BO
CEM
KDE-SO
SGD-CVaR
Refine-only
B=2000
25
24.5
43.5
43.3
48.6
61.2
40.6
B=5000
16
5.3
29.5
10.7
13.6
48.3
15.3
B=10000
19
0.7
10.8
4.5
6.9
12.5
6.1
d=2
16
4.2
20.0
15.9
4.7
17.3
21.1
d=4
16
5.1
20.5
11.8
17.9
35.1
17.7
d=6
11
10.3
26.4
23.3
36.1
45.8
14.3
Table 4: Analytic family: mean normalised regret by budget, dimension and jump regime ( n = number of instances). The lowest value in each row is in bold
Figure 3: External problems: mean normalised regret by budget (thousands of simulator draws) with 95% bootstrap intervals over 20 replications; (a)–(c) development set E1–E3, (d)–(f) held-out set E4–E6. Methods are distinguished by marker shape and line type. The vertical scales differ between panels
Problem
B (k)
ACRS
GP-BO
CEM
KDE-SO
SGD-CVaR
Refine-only
Development set
E1
2
3.8
26.7 +
21.3 +
29.3 +
74.4 +
39.3 +
E1
5
0.4
16.2 +
10.1 +
9.6 +
18.0 +
10.1 +
E1
10
0.3
5.0 +
2.5 +
0.5 +
9.8 +
3.4 +
E2
2
20.1
103.5 +
100.3 +
59.5 +
68.5 +
35.7
E2
5
16.8
31.3 +
38.5 +
36.3 +
64.5 +
39.1 +
Table 5: External problems: median normalised regret over 20 replications. Bold: lowest median in the row. + / - : the competitor is significantly worse/better than ACRS (paired Wilcoxon test over replications, Holm-adjusted over five comparisons, level 0.05)
Figure 4: Analytic family: exact normalised regret of ACRS after the surrogate search, after oracle reranking and after the local refinement, by budget (240 runs; boxes show quartiles, whiskers 1.5 interquartile ranges; values below 0.01 are shown at 0.01)
Variant
Mean regret
Median regret
p
ACRS (full)
11.8
0.5
–
without focused augmentation
16.3
1.0
0.005
without oracle reranking
17.0
2.2
0.004
without tail importance sampling
12.3
0.7
0.333
quadratic location model only
20.2
4.5
< 0.001
kernel weights instead of residual model
15.1
1.0
0.112
Table 6: Ablation of ACRS on the 60 analytic instances (4 replications each). p : two-sided paired Wilcoxon test against the full method on instance means, Holm-adjusted over the six variants
Figure 5: Ablation of ACRS on the 60 analytic instances: mean normalised regret with 95% bootstrap intervals over instances. The dashed line marks the full method
DGP1
DGP2
Conditional model
N=1000
N=5000
N=1000
N=5000
Time (s)
Residual, quadratic location
18.5
6.1
44.6
27.0
1.7
Residual with forest weights
20.7
14.8
44.6
35.1
78.0
Kernel weights
31.5
38.2
74.8
54.2
2.2
Generalised random forest
48.1
29.4
72.4
63.6
85.0
Distributional random forest
52.2
33.6
69.9
66.0
41.3
Table 7: Choice of conditional model (preliminary experiment): median relative gap (%) between the objective at the surrogate minimiser and at the reference optimum, without any simulator draws after the N design draws (15 replications per cell), and median fitting and search time
Table 2: Decision-dependent parameters of DGP2 (Gaussian copula with log-normal marginals); σj is floored at 0.05
Setting
B=2000
B=5000
B=10000
B=30000
ACRS: design n0
200
500
1000
3000
ACRS: augmentation na
100
250
500
1500
ACRS: reranking (at most)
320
320
500
1500
Refinement: sample-path size nℓ
80
80
80
102
Refinement: selection/pilot size ns
150
150
150
170
GP-BO: draws per evaluation
50
50
50
115
Appendix
Table 1: Budget-dependent settings. EI: expected improvement. CEM population: analytic and external problems; on DGP1/DGP2 the population is 30 at every budget
DGP
λ
B (k)
ACRS
GP-BO
CEM
KDE-SO
SGD-CVaR
Refine-only
DGP1
0.5
5
0.5
3.9 +
7.0 +
0.7 +
68.2 +
5.5 +
DGP1
0.5
10
0.2
1.3 +
0.2
0.2
3.7 +
0.2
DGP1
0.5
30
0.1
0.5
0.1
0.1
0.5
0.1
DGP1
0.7
5
1.1
5.5 +
6.5 +
0.7
63.1 +
5.8 +
DGP1
0.7
10
0.1
1.9 +
0.3
0.6 +
3.5 +
0.0
DGP1
0.7
30
0.3
0.2
0.1
0.1
0.8
0.1
Appendix
Table 1: DGP1 and DGP2: median normalised regret over 30 replications. Bold: lowest median in the row. + / - : the competitor is significantly worse/better than ACRS (paired Wilcoxon test over replications, Holm-adjusted, level 0.05)
Dept. of Mathematics, IISER, Pune. · Dept. of Computer Science and Automation, Indian Institute of Sciecne, Bangalore. · The Alan Turing Institute, Greater London, England, UK.