PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Sample Average Approximation

Dimitris Bertsimas, Vishal Gupta, Nathan Kallus

arXiv:1408.4445v3math.OC

TL;DR

Because the distribution is unknown and SAA does not typically provide strong finite-sample guarantees, the paper proposes Robust SAA, a tractable distributionally robust modification based on goodness-of-fit testing. Robust SAA retains SAA-like asymptotic behavior while providing finite-sample guarantees, and the broader testing perspective characterizes related DRO methods and informs applications.

  • Problem

    Unknown distributions require decisions from data, while SAA's strong asymptotic guarantees do not typically extend to finite samples.

  • Method

    Robust SAA approximates SAA with a data-driven distributionally robust optimization problem whose uncertainty set is a goodness-of-fit test confidence region.

  • Results

    Robust SAA combines tractability, finite-sample guarantees, and asymptotic convergence similar to SAA across a wide class of optimization problems.

  • Takeaways & Limitations

    The hypothesis-testing perspective characterizes finite-sample and asymptotic performance of DRO methods and supports practical formulation choices and bootstrapping improvements.

  • Takeaways & Limitations

    Student's T-test bounds may be invalid at the desired probability when the sample size is not practically large enough for its distributional approximations.

Abstract

from arXiv · show

Sample average approximation (SAA) is a widely popular approach to data-driven decision-making under uncertainty. Under mild assumptions, SAA is both tractable and enjoys strong asymptotic performance guarantees. Similar guarantees, however, do not typically hold in finite samples. In this paper, we propose a modification of SAA, which we term Robust SAA, which retains SAA's tractability and asymptotic properties and, additionally, enjoys strong finite-sample performance guarantees. The key to our method is linking SAA, distributionally robust optimization, and hypothesis testing of goodness-of-fit. Beyond Robust SAA, this connection provides a unified perspective enabling us to characterize the finite sample and asymptotic guarantees of various other data-driven procedures that are based upon distributionally robust optimization. This analysis provides insight into the practical performance of these various methods in real applications. We present examples from inventory management and portfolio allocation, and demonstrate numerically that our approach outperforms other data-driven approaches in these applications.

1 Introduction

SAA is tractable and asymptotically convergent, but finite-sample guarantees and stability can be weak. Robust SAA addresses these criticisms by combining distributionally robust optimization with goodness-of-fit testing while retaining tractability and asymptotic behavior.

  • SAA motivation: SAA approximates the unknown distribution with the empirical distribution and is widely used in data-driven stochastic optimization.Its popularity reflects asymptotic convergence and tractability under mild conditions.
  • SAA guarantees: As N → ∞, SAA’s optimal value and an optimal solution converge almost surely to their full-information counterparts.For many cost functions and feasible sets, solving the SAA problem is computationally tractable.
  • SAA limitations: Finite-sample SAA lacks useful a priori performance guarantees in general, while small data changes can cause large changes in solutions and out-of-sample costs.Two-sample SAA sacrifices half the data and can have bounds that depend strongly on the unknown distribution.
  • Robust SAA: Robust SAA defines a distributional uncertainty set as a goodness-of-fit confidence region around the empirical distribution.Different goodness-of-fit tests produce uncertainty sets with different computational and statistical properties.
  • Robust SAA guarantees: Robust SAA combines finite-sample guarantees, asymptotic convergence, and tractable convex optimization for a wide class of cost functions.Many practical cases reduce to linear or second-order cone optimization, and experiments cover inventory management and portfolio allocation.
  • Unified perspective: The paper recasts data-driven distributionally robust optimization through hypothesis testing, linking finite-sample performance to significance and asymptotic performance to consistency.This viewpoint also provides modeling guidance and motivates tools such as bootstrapping.
  • Scope conditions: Robust SAA may lack an optimal solution when the support of the uncertainty is unbounded.For the LCX-based test, uniform consistency remains open when the support is unbounded.

2 Goodness-of-Fit testing and Robust SAA

The paper frames goodness-of-fit tests as confidence-region constructions for data-driven distributionally robust optimization, then uses them to define Robust SAA. This viewpoint also recasts existing data-driven uncertainty sets as hypothesis tests and clarifies their guarantees.

  • Goodness-of-fit testing: A goodness-of-fit test evaluates whether IID data came from a prespecified distribution by rejecting the null only when the statistic exceeds a threshold.The threshold may depend on the true distribution, but not on the data or hypothetical distribution.
  • Goodness-of-fit testing: For continuous distributions, the Kolmogorov-Smirnov test provides a distribution-free threshold computable for finite samples.Its confidence region contains distributions whose cumulative distribution functions remain within the test region around the empirical distribution.
  • Robust SAA: Robust SAA constructs a data-driven distributional uncertainty set as the confidence region of a goodness-of-fit test.Different tests produce uncertainty sets with different computational and statistical properties.
  • Connections to existing methods: A data-driven uncertainty set with finite-sample coverage can be converted into a goodness-of-fit test, creating a common basis for comparing methods.This reverse construction applies to existing data-driven DRO approaches.
  • Connections to existing methods: Testing the entire distribution, rather than only its first moments, is presented as key to obtaining finite-sample guarantees together with asymptotic convergence.The paper uses this perspective to unify discrete and continuous distributions and analyze data-driven DRO.

3 Finite-sample performance guarantees

The paper connects test significance to finite-sample guarantees for Robust SAA and develops tests whose confidence regions support tractable optimization. It also identifies limitations of marginal tests and standard tests on unbounded supports.

  • Finite-sample guarantee: A valid goodness-of-fit confidence region at significance α yields a Robust SAA objective that bounds the true out-of-sample cost with probability at least 1−α.This follows because the uncertainty-set supremum dominates the expectation under the true distribution whenever that distribution lies in the region.
  • Discrete-support tests: The confidence regions produced by discrete-support tests form generalized balls around the empirical distribution whose radius diminishes as O(N^-1/2).The discrete construction uses Pearson’s χ2 test or the G-test, with thresholds obtainable by simulation or asymptotic approximation.
  • Unbounded supports: For unbounded supports and continuous unbounded costs, standard goodness-of-fit uncertainty sets can make the Robust SAA objective infinite almost surely.The paper therefore uses an alternative test designed to preserve finite optimal solutions.
  • Moment control: The paper combines standard goodness-of-fit tests with a generalized-moment test to obtain finite-sample guarantees under growth conditions on the cost function.The moment condition controls costs through a function φ with finite expectation under the true distribution.
  • Multivariate tests: The proposed multivariate approach includes both marginal-distribution tests and a new test based on linear-convex ordering.The LCX-based test has significance level α1+α2 and is designed to test the full joint distribution.
  • Marginal-distribution tests: Marginal tests can require small componentwise significance levels when dimension is large and cannot distinguish distributions with identical marginals.These limitations can adversely affect asymptotic convergence.

4 Convergence

The paper characterizes convergence of Robust SAA through uniform consistency of its underlying goodness-of-fit test. Under stated assumptions, uniform consistency is necessary and sufficient for convergence of objectives, optimal values, and solutions, while weaker test properties can suffice for particular costs.

  • Convergence conditions: Robust SAA convergence requires objective, optimal-value, and optimal-solution convergence almost surely under the paper’s conditions.The conditions include uniform convergence of C(x; F_N) on compact subsets, convergence of optimal values, and convergence of optimal solutions.
  • Convergence characterization: Under the stated assumptions, the confidence region of a uniformly consistent test yields convergence if and only if those assumptions imply conditions (18)–(20).The characterization covers bounded settings for equicontinuous costs and extends to unbounded settings with an additional mild regularity condition.
  • Uniform consistency: Uniform consistency is strictly stronger than ordinary consistency and rejects every non-weakly-convergent distribution sequence infinitely often almost surely.Ordinary consistency concerns a fixed alternative, whereas uniform consistency handles sequences of alternatives simultaneously.
  • Test classes: Classical univariate tests, discrete-support χ2 and G-tests, and bounded-support LCX tests are uniformly consistent.The table also reports that the LCX test is consistent for unbounded support, but uniform consistency there remains an open question.
  • Multivariate tests: Marginal tests are not generally consistent, but they guarantee convergence when costs separate across components and each univariate marginal test is uniformly consistent.A multivariate distribution can differ from the truth while sharing all marginal distributions, preventing rejection from approaching one.
  • DRO tests: Moment-based data-driven DRO tests are not generally consistent because alternatives sharing the true mean and covariance are rejected with probability at most α.Nevertheless, a specific cost function may still exhibit asymptotic convergence even when the underlying test is inconsistent.

5 Tractability

Robust SAA admits tractable reformulations across discrete and univariate settings. Depending on the test and cost structure, the resulting problems can be solved with convex, linear, second-order cone, or polynomial-time oracle-based methods.

  • General tractability: Robust SAA reformulations are tractable for broad cost-function classes and often reduce to linear or second-order cone optimization.General cases can be solved efficiently with cutting-plane algorithms.
  • Discrete support: In the discrete case, ε-optimal solutions can be found in time polynomial in the sample, decision, and support dimensions under the stated oracle assumptions.The complexity is polynomial in n, d_x, K_1, …, K_n, and log(1/ε).
  • Discrete support: Exponential-cone constraints can be recast as second-order cone constraints, although their complexity grows with both n and N.This provides practically usable conic formulations despite numerical challenges associated with exponential-cone optimization.
  • Univariate support: For univariate distributions, semi-infinite conic duality reformulates the DRO problem as a single-level optimization problem.The resulting formulations use canonical cones and support tractability results for several goodness-of-fit-based uncertainty sets.
  • Univariate support: Under the stated oracle assumptions, ε-optimal univariate solutions can be computed in time polynomial in N, d_x, K, and log(1/ε).The result applies to the D_N, V_N, W_N, U_N, and A_N uncertainty-set families.
  • Applications: For the newsvendor problem, solving Robust SAA is no more difficult than solving the corresponding SAA problem.When X is polyhedral and K is fixed at 1 or 2, the reformulation becomes a linear optimization problem whose size grows with N and the dimension of X.
  • Complexity boundary: Reformulation size grows exponentially as 2^K−1, but many examples have K=1 or K=2 and therefore admit single linear optimization formulations.This exponential dependence is the main stated complexity boundary for the piecewise cost representation.

6 Estimating the price of data

The paper defines the price of data as the expected marginal benefit of one additional observation in reducing the cost bound. It proposes resampling-based estimation and discusses a simpler newsvendor approximation.

  • Definition: The price of data is the expected marginal benefit of one additional data point in reducing the bound on costs.The quantity is defined conditional on the present dataset.
  • Estimation: Resampling can estimate the expected marginal benefit of an additional observation.The resampled average can itself be approximated using a smaller random subsample.
  • Newsvendor approximation: For the newsvendor problem with the KS test, a closed-form solution motivates an approximation because small data changes have little effect on x.The approximation also uses that costs near x are smaller than costs far from x.

7 Empirical study

The empirical study finds that Robust SAA combines valid finite-sample guarantees, correct asymptotic convergence, and substantially lower variability than SAA, 2-SAA, and other data-driven approaches across inventory and portfolio applications.

  • Robust SAA yields stable, low-variance solutions while matching SAA and 2-SAA in expected out-of-sample performance for small to moderate N.Its advantage is primarily in out-of-sample variability rather than expected performance.
  • 7.1 Single-item newsvendor and the KS test: In the single-item newsvendor, SAA estimates are downward biased, falling below the full-information optimum 65% of the time for N = 100.This bias can make additional data appear to have a negative price.
  • 7.1 Single-item newsvendor and the KS test: Robust SAA converges to the full-information optimum, provides a valid 1 −↵ bound, and has much smaller order-quantity variance than SAA and 2-SAA for N ≤103.For large N, Robust SAA and SAA variances become indistinguishable on a log scale, while 2-SAA remains more variable.
  • 7.1 Single-item newsvendor and the KS test: Robust SAA’s price-of-data estimate is virtually indistinguishable from the actual price of data on a log scale in the newsvendor problem.
  • 7.5 Portfolio Allocation: In portfolio allocation, Robust SAA outperforms previous methods in average out-of-sample suboptimality and produces the lowest total-variance portfolios.The portfolio model uses a low-dimensional factor structure with long-tailed returns, and lower portfolio variance may reduce transaction costs from rebalancing.

8 Conclusion

The paper introduces Robust SAA, a tractable data-driven optimization method combining SAA, distributionally robust optimization, and goodness-of-fit testing. It connects statistical test properties to finite-sample and asymptotic optimization performance, with numerical evidence of practical advantages.

  • Robust SAA combines tractability and finite-sample performance guarantees with asymptotic behavior similar to traditional SAA.
  • The method’s key idea is a connection between SAA, distributionally robust optimization, and statistical hypothesis testing.
  • The connection links finite-sample and asymptotic optimization performance to the significance and consistency of an associated goodness-of-fit test.
  • Numerical experiments in inventory management and portfolio allocation show that Robust SAA is tractable and can outperform existing data-driven methods.

10 Appendix

The appendix develops validity and computation results for goodness-of-fit thresholds used in the paper’s distributionally robust formulations. It covers closed-form bounds, bootstrap approximations, and tractable solution procedures.

  • The appendix establishes existence of finite minimizers using continuity, coerciveness, and the Weierstrass extreme value theorem.
  • Two threshold-computation approaches are provided: an exact closed-form formula that may be loose and a tighter approximate bootstrap method.
  • For the LCX-based goodness-of-fit test, a valid closed-form threshold is derived using probabilistic bounds involving the sample size and dimension.
  • The derived finite-sample bound holds with probability at least 1 − α1 − α2 for the stated assumptions and parameter choices.
  • The bootstrap estimates a threshold by repeatedly resampling from the empirical distribution and taking an upper quantile of the resulting statistics.
  • Bootstrap computation can yield significantly smaller thresholds while preserving the same asymptotic behavior, though the associated optimization may be non-convex.

10.4 Proof of Proposition 4

This appendix section proves how consistency properties of goodness-of-fit tests control convergence of their confidence regions. It also constructs a consistent but not uniformly consistent test to establish the distinction.

  • Uniform consistency of a goodness-of-fit test implies that its confidence regions converge to the true distribution almost surely.
  • For any fixed alternative distribution G0 different from F, the probability that G0 remains in the confidence region converges to zero.
  • The constructed test has significance α under the null hypothesis and rejects every fixed continuous alternative with probability converging to one.
  • Despite consistency, the constructed test is not uniformly consistent because a sequence of alternatives can remain un-rejected without converging weakly to F.

10.5 Proofs of Theorems 2 and 3

The appendix proves convergence and boundedness properties needed for the paper’s main theorems. Under the stated assumptions, distributionally robust objectives converge to the full-information objective and minimizers remain controlled.

  • Uniformly consistent-test confidence regions yield convergence of worst-case expected costs to the true expected cost for every decision.
  • A convergence condition along every convergent decision sequence implies uniform convergence of the distributionally robust objective on compact decision sets.
  • The arguments use empirical-distribution convergence, equicontinuity, uniform integrability, and coerciveness to establish the required objective convergence.
  • The proof controls minimizing sequences by showing that their decision sets remain bounded under compactness or coerciveness assumptions.
  • Every convergent subsequence of robust minimizers has a limit in the set of full-information minimizers.
  • For bounded support, the appendix verifies assumptions through bounded costs, bounded gradients, and uniform coerciveness.

10.6 Proof of Theorem 4

The proof establishes uniform consistency for goodness-of-fit tests by relating their statistics to total variation, Lévy, or empirical-process distances that vanish uniformly with sample size.

  • Finite-support support: Total variation converges uniformly over the model class for χ2 and G-tests because their rejection threshold scales as Q/N.Q is the (1 − α)th χ2 quantile with n − 1 degrees of freedom and is independent of N.
  • Univariate support: The Lévy metric is bounded by the empirical Kolmogorov distance, so uniform convergence of the latter yields uniform consistency for KS and Kuiper tests.The proof uses dLévy(ˆFN, F0) ≤ DN(F0) ≤ VN(F0).
  • Univariate support: For CvM and AD tests, the relevant test-statistic bound is O(N^-1/2), while the associated rejection threshold is O(N^-1).These rates imply uniform consistency for both tests.
  • Univariate support: The Watson test is uniformly consistent because its corresponding quantity is O(1/N).

10.8 Proof of Proposition 5

The proof derives consistency results by combining almost-sure convergence of moments or expectations with structural assumptions on the distributional ambiguity sets.

  • Cost consistency: Almost-sure convergence of expected costs for every decision implies c-consistency after summing over the cost components.
  • Moment conditions: For ambiguity sets imposing convergence of first and second moments, expected costs converge under covariance existence and bounded operator norm.The proof restricts to sequences with bounded operator norm and eventually belonging to the relevant ambiguity set.
  • Consistency against alternatives: When F0 differs from F, either likelihood-ratio order or a differing second moment leads to rejection probability approaching one.
  • Projection convergence: Convergence of one-dimensional projections at every continuity point, for every projection vector, yields FN converging to F through the Cramer-Wold device.

10.13 Proof of Theorem 9

The proof shows tractability of the distributionally robust optimization formulations by converting inner problems into dual conic or linear programs and constructing weak separation procedures.

  • Tractability: Weak optimization is polynomially reducible to weak separation for the DRO formulations, assuming a weak separation oracle for x ∈ X.The remaining constraints admit tractable separation through standard conic-affine optimization and oracle calls.
  • Tractability: For continuous cost functions, separation over interval-wise maximum constraints uses δ-optimization and subgradient oracles.The resulting hyperplane is valid for the original constraint and separates violated points.
  • Dual reformulation: Linear optimization duality and strong duality transform the measure-based formulation into a finite-dimensional dual problem.The argument invokes a generalized Slater point equal to the empirical distribution.
  • Bounds: For the analyzed bound, τ = 0 is the only feasible choice under one condition and otherwise provides an upper bound by weak duality.

10.18 Proof of Theorem 15

The proof establishes tractable weak separation for the remaining DRO constraint by using a concave-conjugate oracle and subgradients.

  • Tractability: Weak optimization is polynomially reducible to weak separation when all constraints except the target constraint have tractable separation.A weak separation oracle for x ∈ X is assumed available.
  • Separation procedure: The separation procedure first searches for a nearly optimal ξ using a concave-conjugate oracle, then constructs a valid separating hyperplane from a subgradient when violation occurs.
Loading 1408.4445v3…