PaperlayerView exact revision on arXiv

Source-linked AI summary

Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach

John Duchi, Peter Glynn, Hongseok Namkoong

arXiv:1610.03425v3stat.ML

TL;DR

The paper addresses statistical inference for stochastic optimization when the population distribution and objective are uncertain or difficult to compute. It develops generalized empirical likelihood based on nonparametric f-divergence uncertainty sets, yielding exact asymptotic confidence bounds, variance regularization, and SAA-like consistency. The approach extends to dependent stationary sequences, while uniqueness assumptions and computational scalability remain important boundaries.

  • Problem

    Stochastic optimization needs confidence intervals for optimal values and consistent approximate solutions when the population objective is unknown or intractable to compute.

  • Method

    The paper develops generalized empirical likelihood for Hadamard differentiable functionals, using distributionally robust formulations built from general f-divergence balls.

  • Results

    The robust formulations provide asymptotically exact confidence coverage, variance-based regularization, and optimizers with essentially the same consistency conditions as classical SAA.

  • Takeaways & Limitations

    Distributionally robust optimization can simultaneously calibrate confidence bounds and regularize stochastic programs by their objective variance while retaining convexity and risk coherence.

  • Takeaways & Limitations

    The theory imposes stringent uniqueness conditions, and efficient methods for scaling the resulting minimax programs to very large samples remain underdeveloped.

Abstract

from arXiv · show

We study statistical inference and distributionally robust solution methods for stochastic optimization problems, focusing on confidence intervals for optimal values and solutions that achieve exact coverage asymptotically. We develop a generalized empirical likelihood framework---based on distributional uncertainty sets constructed from nonparametric $f$-divergence balls---for Hadamard differentiable functionals, and in particular, stochastic optimization problems. As consequences of this theory, we provide a principled method for choosing the size of distributional uncertainty regions to provide one- and two-sided confidence intervals that achieve exact coverage. We also give an asymptotic expansion for our distributionally robust formulation, showing how robustification regularizes problems by their variance. Finally, we show that optimizers of the distributionally robust formulations we study enjoy (essentially) the same consistency properties as those in classical sample average approximations. Our general approach applies to quickly mixing stationary sequences, including geometrically ergodic Harris recurrent Markov chains.

1 Introduction

The paper develops a generalized empirical-likelihood framework that turns distributionally robust stochastic optimization into statistically calibrated confidence procedures. It establishes exact asymptotic coverage, variance-based regularization, and consistency under broad distributional and dependence settings.

  • Motivation: Unknown or computationally intractable population objectives motivate replacing stochastic optimization with sample average approximation and distributionally robust confidence programs.The framework constructs uncertainty sets around the empirical distribution to infer optimal values and assess approximate solutions.
  • Method: Generalized empirical likelihood applies to smooth functionals, including Topt(P) = inf_x∈X E_P[ℓ(x; ξ)], and extends to stationary dependent sequences.The theory uses general f-divergences and covers settings beyond finitely supported distributions, including suitable quickly mixing sequences.
  • Inference: The robust formulations provide upper and lower confidence bounds for the optimal population objective with asymptotically exact coverage.The interval [l_n, u_n] also admits sharper expansions and shrinking-width rate statements.
  • Regularization: The robust formulation regularizes sample average approximation by a variance-dependent term while preserving convexity and risk coherence.Under mild restrictions, the asymptotic expansion is uniform in x, supporting the regularization interpretation for robust minimizers.
  • Consistency and scope: Robust optimizers have essentially the same consistency conditions as sample average approximation, including under lower semicontinuity and more-than-one-moment assumptions.The paper also identifies self-normalization and exact-coverage advantages relative to normal-based intervals and earlier inexact procedures.

2 Generalized Empirical Likelihood and Asymptotic Expansions

The paper generalizes empirical likelihood to smooth functionals and stochastic optimization, deriving divergence-based confidence guarantees and asymptotic expansions under independent and stationary data.

  • Generalized empirical likelihood: The generalized empirical likelihood confidence region is the image of a functional T over an f-divergence neighborhood of the empirical distribution.A profile divergence provides an equivalent threshold characterization of membership in the confidence region.
  • Inference guarantees: Under the stated assumptions, smooth f-divergence regions yield asymptotically exact confidence regions, including generalized versions of classical chi-square calibration.The framework assumes finite covariance for the i.i.d. vector result and local Lipschitzness, compactness, and moment conditions for uniform expansions.
  • Generalized empirical likelihood: For smooth f-divergences satisfying Assumption A, the framework extends classical empirical likelihood results beyond means and finite-dimensional i.i.d. vectors.The extension covers suitably smooth functionals and includes f-divergences with f(1)=f′(1)=0 and f′′(1)=2.
  • Stochastic optimization: For Topt(P)=infx∈X EP[ℓ(x; ξ)], stronger asymptotic expansions are required to obtain inferential guarantees beyond pointwise confidence intervals.The paper develops uniform expansions for stochastic optimization functionals rather than relying only on fixed-x results.
  • Dependence and extensions: The results extend to strictly stationary ergodic sequences, with the paper providing an almost-sure expansion that generalizes an in-probability empirical-likelihood result.The stationary-sequence argument uses ergodicity and applies beyond the independent case.
  • Asymptotic expansions: The expansion’s second term acts as a variance-based regularizer for the sample average approximation, uniformly in x under mild restrictions.The regularizer can be non-convex in x even when the loss is convex, and the interpretation applies when robust formulations are minimized.

3 Statistical Inference for Stochastic Optimization

The paper develops generalized empirical likelihood confidence bounds for stochastic optimization, extending them to smooth optimal-value functionals and quickly mixing dependent sequences. Under suitable conditions, the bounds achieve asymptotically exact coverage, with computational procedures for the upper and lower endpoints.

  • Generalized empirical likelihood: Hadamard differentiability of the optimal-value functional enables generalized empirical likelihood confidence bounds for stochastic optimization.The result covers general constraints and broader losses and divergences than an estimating-equations approach.
  • Generalized empirical likelihood: Unique population minimizers yield asymptotically exact confidence intervals for the optimal population objective.The result applies first to i.i.d. data and supports one- and two-sided bounds.
  • Confidence coverage: The generalized empirical likelihood formulation is asymptotically pivotal, unlike the normal approximation, which depends on the unknown variance of the optimal loss.Normal intervals typically estimate Var bPn(ℓ(bxn; ξ)), whereas the empirical likelihood approach requires no hidden variance quantity.
  • Confidence coverage: A one-sided interval (−∞, un] attains asymptotic coverage 1 −α when ρ is set to χ2_1,1−α.This correction shortens the confidence set for an upper-bound requirement.
  • Dependent sequences: The framework extends to stationary β-mixing sequences and suitably fast-mixing Harris recurrent Markov chains.The dependent-sequence result uses mixing and moment conditions, and includes geometrically β-mixing uniformly ergodic chains.

4 Connections to Robust Optimization and Examples

The robust formulation connects generalized empirical likelihood with coherent risk measures and variance-regularized optimization. It addresses SAA optimism, recovers higher-order risk formulations, and approximates a Markowitz objective while retaining a distinct downside-risk interpretation.

  • Robust optimization connections: The robust objective is a coherent risk measure that addresses SAA optimism through a worst-case objective over an f-divergence confidence region.It is convex, monotonic, translation equivariant, and positively homogeneous in the loss.
  • Risk measures: Cressie-Read divergences recover higher-order risk formulations whose asymptotic upper confidence bounds have exact coverage for each parameter k.The family includes χ2-divergence, empirical likelihood, and KL-divergence.
  • Variance regularization: The robust expansion penalizes loss variance and thereby ameliorates the optimism bias of standard sample average approximation.The resulting variance regularizer can be used to approximately solve a convex optimization problem, although the variance-penalized objective is generally non-convex.
  • Variance regularization: The robust formulation approximates the Markowitz objective to o_p(n^-1/2) while penalizing downside risk only, unlike Markowitz variance penalization.For linear losses, the variance-penalized objective is convex and efficiently minimizable.

5 Consistency

Robust minimizers are consistent under conditions essentially comparable to those for sample average approximation. The paper establishes this through uniform convergence on compact domains and epigraphical convergence for convex losses on potentially unbounded domains.

  • Consistency guarantees: Robust minimizers are consistent under essentially the same conditions required for sample average approximation.The paper proves this using uniform convergence and epigraphical convergence.
  • Epigraphical convergence: The convex analysis permits unbounded feasible regions because growth of the population objective away from the solution set prevents distant spurious minimizers.The theorem also generalizes to dependent sequences when the relevant pointwise strong law holds.
  • Uniform convergence: The uniform-convergence results extend from i.i.d. samples to β-mixing sequences.Glivenko-Cantelli properties for i.i.d. data carry over under β-mixing dependence.
  • Uniform convergence: Uniform convergence of the robust objective to the population risk yields consistency when the feasible region is compact and the loss class is Glivenko-Cantelli.The stated envelope condition requires more than one moment of the objective.
  • Epigraphical convergence: For convex losses, epigraphical convergence bypasses the compactness and uniform-convergence conditions used in the compact-domain analysis.The alternative requires moment, lower-bound, and convergence conditions and relies on compactness of the solution set rather than boundedness of X.

6 Simulations

Simulations evaluate generalized empirical likelihood and normal confidence procedures in portfolio, CVaR, and newsvendor optimization. Coverage approaches the nominal 95% level at large sample sizes, but convergence is slower for heavy-tailed data and small-sample undercoverage occurs in several settings.

  • Experimental design: Three experiments compare generalized empirical likelihood and normal confidence procedures for portfolio, CVaR, and multi-item newsvendor optimization.Each experiment uses independent replications and reports coverage behavior across sample sizes.
  • Overall coverage: 95% nominal coverage is closely approximated at the largest reported sample size for both light-tailed and heavy-tailed simulations.The study uses samples up to n = 10,000 for light-tailed and n = 100,000 for heavy-tailed distributions.
  • Portfolio optimization: In portfolio optimization, the robust/empirical likelihood interval at n = 20 is approximately [−150, 40], while generalized empirical likelihood undercovers relative to the normal interval in small samples.The SAA objective is optimistic, whereas the Markowitz estimate is somewhat conservative.
  • Conditional value-at-risk: In CVaR optimization, empirical likelihood coverage is generally below normal coverage because negative bias remains in the robust estimator.Coverage converges more slowly for heavy-tailed data with β ∈{3, 5}.
  • Multi-item newsvendor: In the multi-item newsvendor experiment, generalized empirical likelihood coverage remains below the nominal 95% level but differs less from nominal coverage than in other cases.Figure 1c compares average empirical-likelihood-based and normal-based confidence intervals.

7 General Results

This section develops general empirical-process and generalized empirical-likelihood results for smooth functionals, including stochastic optimization and quickly mixing dependent sequences.

  • General framework: The framework applies to Hadamard differentiable functionals and P0-Donsker classes with L2-integrable envelopes.The general treatment is needed because Frechet differentiability is too restrictive for constrained stochastic optimization.
  • Empirical likelihood: The generalized empirical-likelihood theory extends confidence-set calibration from means to smooth functionals, including Topt(P) = inf_x∈X EP[ℓ(x; ξ)].The theory uses influence functions and requires a nondegenerate finite variance for the influence function.
  • Dependent sequences: Bracketing entropy conditions extend the results to strictly stationary β-mixing sequences.For i.i.d. data, the relevant bracketing norm reduces to the usual L2(P0)-norm.

8 Conclusion

The conclusion summarizes generalized empirical likelihood as a distributionally robust approach with exact asymptotic coverage, variance-based regularization, and consistency guarantees. It also identifies stringent uniqueness assumptions, computational scaling challenges, and unresolved finite-sample effects of divergence choice.

  • Main conclusions: The robust upper-confidence formulation provides exact asymptotic coverage while preserving convexity and risk coherence.Its asymptotic expansion interprets robustification as regularization by variance.
  • Open statistical issues: Theorem 3’s uniqueness conditions are stringent, and adaptive procedures for non-singleton solution sets remain an open problem.Without uniqueness, the asymptotic distribution of solutions is no longer normal, complicating inference.
  • Computational issues: Interior-point algorithms can be too expensive for very large samples because objective or gradient evaluation requires time at least linear in n.Efficient methods for scaling minimax robust optimization remain underdeveloped relative to SAA and stochastic-gradient methods.
  • Calibration and divergence choice: The calibration parameter ρ can be chosen statistically for confidence bounds, while smooth f-divergences share the same first-order asymptotic behavior.Their higher-order and finite-sample effects in large-scale optimization remain unresolved.

A.1 Proof of Lemma 6

This proof compares smooth approximations to the f-divergence constraint with tractable quadratic and bounded perturbation sets, then bounds their support functions to obtain the variance expansion.

  • Auxiliary lemmas: The auxiliary lemmas establish the lower and upper bounds needed to prove Lemma 6.The argument combines the support-function estimates after centering z.
  • Divergence approximation: A C3 divergence with f′′(1) = 2 is bounded above and below near 1 by quadratic expressions.These inequalities create the small and large feasible sets used in the comparison.
  • Feasible-set comparison: The proof rewrites the supremum over divergence-feasible weights and compares it with sets constrained by ℓ∞ and ℓ2 bounds.The lower and upper support-function bounds are handled separately.
  • Upper bound: Lagrangian duality and one-dimensional maximization control the upper support-function bound.The multiplier is bounded below by ∥z∥∞/(εn), which yields the needed estimate.

B.1 Preliminary results and definitions

This section supplies probability and empirical-process foundations for the paper’s weak-convergence, delta-method, and robust-expansion results. It establishes tightness, Donsker-process control, and functional linearization in the required spaces.

  • Weak convergence: Tightness and finite-dimensional convergence together characterize weak convergence to a tight limit in L∞(H).These results provide the main convergence criterion for the empirical processes used later.
  • Robust empirical processes: For P0-Donsker classes with L2-integrable envelopes, √n(Qn − P0) is asymptotically tight for every Qn in the divergence neighborhood.A preceding lemma controls how close the feasible density weights remain to the all-ones vector.
  • Uniform control: The resulting uniform expansions combine tightness, Donsker convergence, and uniform Glivenko-Cantelli control.These ingredients make the robust functional expansion uniform over the divergence neighborhood.
  • Functional delta method: Hadamard differentiability permits the delta method to linearize T(Qn) around T(Q) through its derivative.The remainder is represented by κ(P) = T(P) − T(P0) − EP[T(1)(ξ; P0)].

C.3 Proof of Theorem 4

The proof derives the upper confidence bound using Gaussian-process limits and the delta method, with the lower-bound argument analogous. It also establishes the population optimizer characterization and evaluates the conjugate needed for the robust formulation.

  • Confidence bounds: The upper confidence bound is proved asymptotically; the lower confidence-bound proof is stated to be completely parallel.The argument invokes Theorem 9 and Gaussian processes H+ and H−.
  • Confidence bounds: The delta method transfers the Gaussian-process result through the infimum functional, relying on its continuity in the sup-norm topology.The proof refers to Theorem 3, Section C.1, and Lemma 17.
  • Optimizer characterization: The population optimizer set is characterized as P0 = argminx∈X EP0[ℓ(x; ξ)], with the singleton case immediate.The passage identifies this characterization as the theorem’s first claim.
  • Conjugate calculation: The conjugate calculation splits according to the sign of s and solves the first-order condition when the interior maximizer applies.For s < 0, the supremum occurs at t = 0; for the other case, differentiation gives the optimizing t.
  • Conjugate calculation: Substituting the optimized dual variable and mapping ρ to ρ/n yields the lemma’s stated result.The derivation uses the duality representation for Z = ℓ(x; ξ).

D.1 Proof of Example 3

This proof extends the asymptotic theory to geometrically ergodic Markov chains and general initial distributions. It verifies mixing, differentiability, integrability, and convergence conditions needed for the stochastic optimization results.

  • Mixing conditions: Geometric ergodicity implies βn = O(sn) after bounding the weighted transition distance and taking expectations under the stationary distribution.The argument uses aperiodicity, positive Harris recurrence, and geometric ergodicity.
  • Functional conditions: The stochastic optimization functional is Hadamard differentiable, while Lipschitz losses and moment conditions verify the empirical-process hypotheses.Compactness of X and integrability of the loss and Lipschitz modulus are used in the verification.
  • Initial distributions: The robust optimization result for infima over divergence balls follows analogously after replacing the empirical distribution with the relevant empirical distribution over the dependent observations.The proof states that the corresponding result for infima is analogous.
  • Initial distributions: For stationary initialization, the normalized statistic converges in distribution to W, and total-variation convergence transfers this result to any initial distribution.The proof uses an increasing burn-in sequence and positive Harris recurrence.

D.4 Proof of Proposition 6

The proof establishes the variance expansion by controlling blockwise moments and showing asymptotic covariance terms vanish. It then combines these bounds with mixing and symmetrization arguments to obtain the proposition’s result.

  • Proof setup: The proof begins under stationary initialization and states that the general-initial-distribution case follows by a similar argument.The analysis introduces quantities Nj and treats the j = 2 case separately.
  • Asymptotic expansion: The centered block quantities jointly converge to a normal distribution with specified marginal distributions.The proof uses a remainder term εb,j and Cramer’s device.
  • Asymptotic expansion: Showing that the block quantities have asymptotic covariance zero yields the desired variance expansion.The proof bounds covariance terms using β-mixing coefficients and related mixing inequalities.
  • Moment control: Moment bounds for Nj depend on the loss-modulus moments, the diameter of X, and a constant determined by f, ρ, r, and diam(X).Lemma 19 supplies the blockwise moment control under Eπ[M(ξ)2r] < ∞.
  • Error control: A decomposition of the relevant terms is controlled using chaining, symmetrization with independent random signs, and bounds from Lemma 13.These estimates bound both components of the variance-expansion error.
  • Error control: The resulting bounds establish the final proposition after taking expectations and combining the two terms in the decomposition.The conclusion follows from the preceding inequalities and expectation bounds.

E.2 Proof of Theorem 8

The proof shows that the sample-based robust upper-bound objective epi-converges to the population risk and that its minimizers remain eventually localized near the population optimizer set.

  • Epi-convergence: Epi-convergence is characterized through Painlevé–Kuratowski convergence of epigraphs and, for closed convex functions, pointwise convergence on a dense set.The proof recalls the relevant definitions and the Rockafellar–Wets characterization.
  • Objective convergence: The sample and population robust objectives are closed convex, and moment assumptions yield pointwise almost-sure convergence of the sample objective to the population objective.The argument uses the strong law and continuous mapping theorem.
  • Objective convergence: The pointwise convergence extends to epi-convergence with probability one under the stated convexity and regularity conditions.The proof verifies the relevant condition through convergence on a dense subset and uniform control on compact sets.
  • Minimizer localization: Compactness of population sublevel sets and the optimizer set allows a compact neighborhood C to separate the boundary objective values from the minimum.This separation forces empirical minimizers into the interior of C eventually.
  • Minimizer localization: Epi-convergence then gives convergence of the sample robust optimal values to the population optimal value.The proof applies the infimum convergence result for epi-convergent functions.
Loading 1610.03425v3…