PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Scenario Generation for KL-DRO Around a Learned Density Model

Aron Brenner, Saurabh Amin

arXiv:2610.40644v1eess.SYcs.LGcs.SY

TL;DR

Data-driven two-stage DRO must hedge against distribution error while standard ambiguity sets treat realizations absent from the record differently. The paper centers a KL ball at a learned density model and adaptively constructs importance-weighted scenarios; across two case studies, its advantage is greatest with scarce records and learned structure, and fades as records grow or shifts depart from that structure.

  • Problem

    Standard ambiguity sets either restrict reweighting to recorded realizations or admit unobserved ones without using learned dependence to distinguish plausible from implausible events.

    Source: §1 · p. 1

  • Method

    The method centers a KL ambiguity ball at a density model fitted to the record and adaptively samples toward the current worst case, weighting scenarios back to the learned nominal.

    Source: §1 · p. 2, §2 · p. 3, §4 · p. 4

  • Results

    The learned nominal helps most when records are short and the model extrapolates along learned structure; its advantage fades as records grow, while transport around the record hedges more cheaply against shifts the model does not anticipate.

    Source: §6 · p. 10

  • Takeaways & Limitations

    The learned nominal is most useful when a scarce record supports structure that the model can use to extrapolate to relevant unrecorded events.

    Source: §6 · p. 10

    Both case studies use linear recourse, the radius is chosen empirically without a finite-sample guarantee, and convergence of the returned plan is not shown.

    Source: §6 · p. 10

Abstract

from arXiv · show

Distributionally robust optimization (DRO) hedges data-driven two-stage stochastic programs against error in the distribution estimated from a finite record, and standard ambiguity sets differ in how they treat realizations absent from that record. A divergence ball around the empirical distribution contains only reweightings of the record, whereas a transport ball also contains distributions supported off the record, including on realizations the data-generating process cannot produce, against which the decision is then hedged as well. We instead propose a Kullback-Leibler (KL) ball centered at a density model fitted to the record, the learned nominal, which lets the adversary up-weight costly unobserved realizations in proportion to the probability the model assigns them. Solving the resulting problem poses a second difficulty, because it can accommodate only a few scenarios, and an independent sample of that size is likely to omit the rare realizations on which the worst case concentrates. We therefore build the scenario set adaptively, alternating between solving the finite problem and drawing new realizations from the learned nominal, steered toward the worst case at the current decision, with importance weights that correct the draws back to the model. On a multi-item newsvendor problem and a capacity expansion problem on realistic grid data, centering the ball at the learned nominal rather than at the record lowers cost under distribution shift, at comparable in-distribution cost, when the record is scarce and the model class captures structure that lets it extrapolate beyond the record. The advantage fades as the record grows or as the shift departs from the structure the model has learned.

1 INTRODUCTION

Data-driven DRO can either restrict the adversary to reweighting recorded realizations or admit unobserved ones without using learned dependence to distinguish plausible from implausible events. The paper centers a KL ball at a learned density model and adaptively builds a weighted scenario set, evaluating the approach on newsvendor and capacity expansion problems.

1 INTRODUCTION

  • A learned nominal addresses two gaps: standard ambiguity sets do not use tail dependence to distinguish plausible unobserved realizations, and fixed finite scenario sets can miss rare worst-case events.The paper proposes using the model both as the ambiguity-set center and as a source of scenarios.Source: §1 · pp. 1–2
  • The proposed KL ball is centered at a density model fitted to the record, allowing costly unobserved realizations to be up-weighted in proportion to the model’s assigned probability.The model may be a normalizing flow, Gaussian copula, or diffusion model.Source: §1 · p. 2
  • Adaptive importance sampling builds the scenario set by alternating finite-problem solves with draws steered toward the current decision’s worst case and weighted back to the learned nominal.The radius is chosen empirically because centering at a learned nominal gives up the finite-sample guarantees of record-centered balls.Source: §1 · p. 2
  • The framework is evaluated on a controlled multi-item newsvendor problem and capacity expansion over a 20-zone network using realistic demand and renewable data.The capacity expansion evaluation includes an out-of-distribution test year.Source: §1 · p. 2

2 BACKGROUND

The background formulates risk-averse stochastic programming with a finite scenario approximation and identifies two choices: which realizations the adversary can reach and which scenarios represent the nominal in the solved problem. It then motivates a learned nominal and importance-weighted adaptive scenario construction.

Risk-averse stochastic programming

  • The mean–CVaR objective combines typical and tail costs, while the analysis assumes recourse is feasible and bounded for every decision and nominal-supported realization.Its tail level is α and β weights the tail component.Source: §2 · pp. 2–3

Kullback–Leibler DRO

  • A KL ambiguity set reweights only realizations supported by its nominal, and dualizing its constraint makes the inner maximization a minimization under stated finiteness conditions.With an empirical nominal, the set changes probabilities only for recorded scenarios.Source: §2 · p. 3
  • For a finite nominal, the reformulation is a convex program under convexity conditions, with one recourse copy per scenario and a risk-measure variable.The empirical distribution is the special case with equal weights on all recorded scenarios.Source: §2 · p. 3

Ambiguity centered at a learned nominal

  • A learned density model places mass between and beyond recorded realizations according to learned dependence, so a KL ball around it can include unrecorded events while also hedging against model error.A deterministic decoder of a standard normal enables sampling and exact importance weights.Source: §2 · p. 3

Finite scenario approximation

  • Because the finite master grows with each scenario, adaptive sampling targets decision-sensitive realizations and normalizes importance weights back to the learned nominal.Independent draws can miss rare decision-driving events, and a fixed pool cannot supply realizations it lacks.Source: §2 · p. 3

3 RELATED WORK

Related work distinguishes ambiguity-set designs by how they handle unobserved realizations, scenario-construction methods by whether they use the downstream decision, and generative optimization methods by the role assigned to the generator. The paper positions its approach as centering a divergence ball at a generator while retaining a two-stage objective and exact likelihood ratios.

Ambiguity sets

  • Empirical divergence balls exclude unobserved realizations, transport sets admit them using distance from recorded points, and moment sets constrain low-order statistics.Some related approaches learn a transport cost or nominal instead.Source: §3 · p. 4

Scenario construction

  • Existing scenario methods construct sets from moments, probability metrics, decision-based dissimilarity, implementation error, or tail-risk regions, but construct them before solving.The paper contrasts these with importance sampling that adapts its proposal to the decision.Source: §3 · p. 4

Generative models in optimization

  • Prior generative optimization work samples scenarios, trains generators on decision loss, or optimizes over generator parameterizations; this paper instead centers a divergence ball at the trained generator.The paper states this leaves the generator as trained, gives the worst case in closed form, and keeps likelihood ratios exact.Source: §3 · p. 4

4 ADAPTIVE IMPORTANCE SAMPLING ALGORITHM

The algorithm alternates finite-master solves with adaptive draws aimed at the current decision’s worst case, weighting the draws back to the learned nominal. It uses latent-space tilting and two batch-construction options to target costly scenarios while controlling how the scenario set is built.

4 ADAPTIVE IMPORTANCE SAMPLING ALGORITHM

  • Adaptive importance sampling alternates master solves with draws steered toward the current decision’s worst case and weighted back to Qθ.Source: §4 · p. 4

4.1 ALTERNATING MASTER AND SAMPLER

  • Rounds add nominal-corrected batches and re-solve over held scenarios; joint weight normalization biases the master estimate, while fixed worst-case weights offer a cheaper alternative.Source: §4.1 · p. 5

4.2 THE SAMPLING TARGET

  • In latent space, reweighting standard Gaussian φ is equivalent to the learned-nominal KL ball; cost-tilting targets costly scenarios but can miss costs decisions cannot mitigate.Source: §4.2 · p. 6

4.3 DRAWING THE BATCH

  • Resampling stays within the initial M scenarios; a defensive Gaussian proposal can reach beyond them with exact bounded weights, but its fit degrades with dimension.Source: §4.3 · p. 7
  • The fitted proposal helps most when worst-case events are rare in the initial sample and the latent target is near-Gaussian; nonlinear decoding or limited scenario range weakens its advantage.Source: §4.3 · p. 7

5 EXPERIMENTS

The experiments compare method cost frontiers on a shifted multi-item newsvendor and Texas capacity-expansion planning problem. The learned-nominal methods perform best when short records and model structure support extrapolation, while their advantage narrows with more data or shifts the model does not capture.

5 EXPERIMENTS

  • The studies compare OOD and ID cost frontiers because stronger hedging can reduce OOD cost while increasing ID cost.The newsvendor evaluates four shifts and reads its frontiers through held-out-record selection and the ID cost needed to halve SAA’s OOD cost.Source: §5 · pp. 7–8, §5.1 · p. 8

5.1 MULTI-ITEM NEWSVENDOR WITH SUBSTITUTION

  • At N = 16, KL-Gen-P with a log-normal or flow halves SAA’s OOD cost at about one-third the ID cost required by W-DRO and KL-OT.At larger N, W-DRO leads or ties under the tail shift and overtakes KL-Gen-P under level and support shifts as N grows.Source: §5.1 · p. 8, Table 1 · p. 8
  • KL-Gen-P remains lowest under the coincidence shift because its fitted nominal assigns mass to joint shocks, whereas transport must move every product of a record point together.The shift creates joint shocks while leaving the marginals unchanged.Source: §5.1 · pp. 8–9

5.2 CAPACITY EXPANSION PLANNING

  • Adaptive sampling lowers cost relative to static record-day sets, while KL-Gen’s advantage over KL-OT shrinks as the record grows.The comparison uses a shared mean–CVaR objective and at most 48 scenarios in the capacity-planning study.Source: §5.2 · pp. 9–10
  • At k = 1/2, KL-Gen is cheaper out of distribution than KL-OT at all 15 radius pairs, with its margin falling from 2.3–6.5 bn$/yr to 0.07–0.76 bn$/yr at k = 5.At k = 5, KL-Rec joins the Pareto front; SAA, CSSC, and W-DRO never reach it.Source: Figure 2 · p. 9, §5.2 · p. 10
  • The capacity-expansion flow reproduces the severity and spatial coherence of the most severe 2020 days, including patterns present in a half-year record.Those days are severe when high demand coincides with low renewable output across zones.Source: §5.2 · pp. 9–10

6 CONCLUSION

The paper concludes that learned-nominal KL-DRO helps most with short records when the model captures structure supporting extrapolation, while transport can be cheaper for shifts the model misses. The appendix passages describe the test problem, shift families, and learned nominals used in the newsvendor study.

6 CONCLUSION

  • Across both case studies, the learned nominal helps most with short records when its model class extrapolates along structure visible in the record; its advantage fades as records grow.Transport around the record hedges more cheaply against shifts the model class does not anticipate.Source: §6 · p. 10
  • Both case studies use linear recourse; integer and nonlinear convex recourse remain untested, and the empirically chosen KL radius has no finite-sample guarantee.The authors also report that the master objective is a biased estimate and do not show convergence of the returned plan.Source: §6 · p. 10

A.1 PROBLEM

  • The newsvendor’s upper-tail ordering follows from a high critical ratio, and mean–CVaR raises orders further into the demand tail.The recourse problem allows unmet demand to be substituted from the next product’s stock or lost at a penalty.Source: §A.1 · p. 14

A.2 DISTRIBUTIONS AND RECORDS

  • The newsvendor uses a five-product substitution problem with a known Gaussian-mixture demand distribution and four shifts, including joint shocks with unchanged marginals.Records contain 16, 32, 64, or 128 periods.Source: §A.2 · pp. 14–15

A.3 LEARNED NOMINALS

  • The learned-nominal comparison includes Gaussian, copula, log-normal, mixture, and flow models; the copula remains within the record’s range while other nominals extrapolate beyond it.At N = 16, cross-validation leaves the flow at its log-normal initialization.Source: §A.3 · p. 15, Figure 4 · p. 16

A.4 METHODS

The appendix compares methods that vary scenario source, selection, and hedging, and reports implementation and solver details. Its parity accounting notes that evaluation counts and KL-OT’s larger setting grid favor the baselines.

A.4 METHODS

  • KL-Rec applies KL-DRO to the empirical distribution, while SAA is KL-Rec at radius zero.W-DRO moves all record points; KL-OT moves a tilt-selected subset within a KL ball.Source: §A.4 · p. 16
  • KL-Gen resamples nominal draws by their tilt, while KL-Gen-P draws from a fitted proposal; CSSC reduces a generated pool to weighted medoids.The oracle uses the true distribution only as a reference.Source: §A.4 · p. 16
  • The reported evaluation counts and KL-OT’s 91-setting grid favor the baselines over KL-Gen and KL-Gen-P.KL-Gen and KL-Gen-P each evaluate recourse 356 times per record, while KL-OT uses about 1,300 evaluations per setting at N = 16 and 8,400–9,700 at N = 128.Source: §A.4 · p. 16

A.5 SOLVING THE MASTER

  • The master is a linear program at ρ = 0 and otherwise an exponential-cone program, with sequential least squares programming used as a fallback for some solves.The fallback served 10% of master solves with ρ > 0 and 22% of KL-Gen-P solves.Source: §A.5 · p. 17

A.6 SELECTION AND EVALUATION

Evaluation selects settings on one record half using in-distribution cost and scores them on the other half. Costs are computed under the record and shifted distributions using a common objective and quadrature procedure.

A.6 SELECTION AND EVALUATION

  • Settings are selected on one record half as the largest whose mean ID cost is within 5 percentage points of SAA, then scored on the other half without consulting the shifted distribution.A separate frontier reading uses the lowest median ID cost among settings whose median OOD cost is at most half of SAA’s.Source: §A.6 · p. 17
  • Reported ID and OOD costs are percentages above each distribution’s optimum, estimated with 4,096-point-per-component scrambled Sobol quadrature and summarized by record medians.The reported standard error is 1.2533 times the estimated interquartile-range scale divided by the square root of the number of records.Source: §A.6 · p. 17

A.7 FULL RESULTS

The full-results materials identify the newsvendor comparisons and their reporting criteria, while the capacity expansion model specifies a fixed-budget, zonal planning problem.

A.7 FULL RESULTS

  • Figure 5 organizes newsvendor cost frontiers by record size and shift, with lower-left positions indicating better out-of-distribution and in-distribution costs.The open square marks SAA, and the dashed line marks half of SAA’s out-of-distribution cost.Source: Figure 5 · p. 18
  • Table 3 reports newsvendor costs above optimum under four shifts, including median out-of-distribution cost and the in-distribution cost needed to halve SAA’s out-of-distribution cost.The table covers N = 16 across 300 records; the supplied materials identify Tables 4–6 as corresponding results for N = 32, 64, and 128.Source: Table 3 · p. 19, Table 4 · p. 19, Table 5 · p. 20

B.1 MODEL

  • The capacity expansion model groups ERCOT counties into 20 zones connected by 40 candidate transmission lines and uses a fixed capital budget of 21.5 bn$/yr.At budgets 10% above or below this value, KL-Gen remains cheaper out of distribution than KL-Rec and KL-OT at the stated radius pair.Source: §B.1 · p. 21

B.2 DATA AND RECORDS

The capacity expansion study uses hourly county-level ERCOT data aggregated into daily scenarios and evaluates learned copula and flow nominals fitted to records. The flow has higher held-out likelihood in the reported study, while both nominals overstate tail frequency and the flow’s most severe scenarios have a noted spatial-coherence mismatch.

B.2 DATA AND RECORDS

  • Each daily scenario contains 20 zonal demands and 40 zonal capacity factors, giving D = 1,440 dimensions.The source is hourly county-level ERCOT demand and renewable capacity-factor data aggregated to 20 zones.Source: §B.2 · p. 21
  • 2020 was designated out of distribution and had an annual peak demand of 77.4 GW, 2.5 standard deviations above the 2001–2019 trend.Its 99th-percentile daily peak net load was 50.4 GW, compared with at most 46.7 GW in any other year.Source: §B.2 · p. 23

B.3 LEARNED NOMINALS

  • The flow’s held-out log-likelihood exceeded the seasonal Gaussian copula-form model in each of ten years, by a median 0.97 nats per day with 182 training days and 1.85 with 320.The flow configuration was fixed before any plan was scored.Source: §B.3 · p. 23
  • Both nominals overstate the decade’s tail frequency, and the most severe KL-Gen scenarios have less spatially coherent solar profiles than the most severe 2020 real days.At k = 1 2, the tail-frequency shares are about 1.7 times the decade’s share for the copula and 2.1 times for the flow; solar-profile correlations are 0.82 versus 0.87.Source: §B.3 · p. 23

B.4 METHODS

The methods build finite scenario sets through an adaptive loop, varying scenario source, selection, and hedging approach. In the capacity expansion implementation, each round solves using weights computed at the current plan, so the reported plan is not necessarily optimal for the final scenario set.

B.4 METHODS

  • Each of twelve rounds evaluates 256 candidates and admits four scenarios, so the master holds at most 48 scenarios.The master recomputes the worst case at the current plan and solves for the next plan.Source: §B.4 · p. 23
  • KL-Gen draws from the learned flow, KL-Gen-P uses a fitted proposal, and both select scenarios by the current-decision tilt and hedge with a KL ball.KL-Rec removes generation, KL-OT transports record scenarios, and SAA uses none of these components.Source: §B.4 · p. 24
  • KL-OT moves record days toward higher cost, while W-DRO uses 48 uniformly weighted record days and moves each round’s candidates.At δ = 1, 68 of 100 W-DRO runs reach the four-round cap.Source: §B.4 · p. 24

B.5 SOLVING THE MASTER

  • The reported plan is a best response to the worst case at the preceding plan, not a solution of KL-DRO on the final scenario set.The optimality-gap bound is under 0.7% of the objective for typical runs, but exceeds 0.5 bn$/yr in 36 of 200 runs.Source: §B.5 · p. 25

B.6 EVALUATION AND STATISTICS

Evaluation uses uniform weights over in-distribution or out-of-distribution days, summarizes paired method differences at the record level, and reports development-data reuse. The figure descriptions compare the severity and spatial shape of admitted scenarios with real days, while cautioning that shape proximity alone does not establish realism.

B.6 EVALUATION AND STATISTICS

  • The final plan is scored with uniform weights over all in-distribution or out-of-distribution days.Paired method differences are summarized by their median over five seeds, with the record as the unit of analysis.Source: §B.6 · p. 25
  • The flow architecture and training were fixed before scoring, but radii, risk weight, nominal marginals and smoothing, and base-weight construction were chosen using evaluation days.The in-distribution and out-of-distribution days therefore also served for development.Source: §B.6 · p. 25
  • KL-Gen’s most severe scenarios lie 0.424 from the nearest real day, versus 0.367 for real days of the same severity and 0.372 for KL-OT.After demand rescaling, the three methods’ shape distances are nearly the same, and a small distance does not prove realism.Source: §B.6 · p. 26

B.7 FULL RESULTS

In capacity expansion, KL-Gen has lower out-of-distribution cost than KL-Rec and KL-OT across the tested radius pairs, while its advantage generally shrinks as records grow. Its in-distribution cost is comparable in some settings but can be higher, and replacing the copula with a flow changes out-of-distribution cost little.

KL-Gen vs. KL-Rec

  • KL-Gen’s out-of-distribution cost is lower than KL-Rec’s by 12.7–22.2 bn$/yr at k = 1 2, 8.4–14.5 bn$/yr at k = 1, and 3.8–13.8 bn$/yr at k = 5.It is cheaper in 10 of 10 records at k = 1 2, 5 of 5 records at k = 1, and 5 of 5 blocks at k = 5.Source: §B.7 · p. 26

Record length

  • The out-of-distribution gap to KL-Rec and KL-OT (δ = 1) shrinks as records grow; KL-OT (δ = 3) narrows it at k = 1 2 but raises in-distribution cost.Figure 8 reports paired cost differences across record lengths.Source: Figure 8 · p. 27, §B.7 · p. 27

KL-Gen vs. KL-OT

  • KL-Gen’s out-of-distribution cost is lower than KL-OT’s at all 15 radius pairs, by 2.3–6.5 bn$/yr at k = 1 2, 0.4–1.9 bn$/yr at k = 1, and 0.07–0.76 bn$/yr at k = 5.At k ≥1, KL-Gen costs up to 0.45 bn$/yr more in distribution and is cheaper in at most 3 of 5 records.Source: §B.7 · p. 27

Ablations

  • Replacing the copula with the flow changes out-of-distribution cost little, while adding a small in-distribution premium when the record is longer.At k = 5, KL-Gen is cheaper by 0.31 and 0.84 bn$/yr at two radius pairs; the copula is up to 0.36 bn$/yr cheaper in distribution at k ≥1.Source: §B.7 · p. 27

Related papers

Loading 2610.40644v1…