Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach

By John C. Duchi, Peter W. Glynn, Hongseok Namkoong. 2016

378 citations recorded by the source corpus.

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.

Subfields: Management Science and Operations Research, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Improving Neural Language Modeling via Adversarial Training (2019, background): “In statistics learning and robust statistics, various adversarial-like ideas are also leveraged to construct efficient and robust estimators, mostly for preventing model specification or data corruption (e.g., Maronna et al., 2018; Duchi et al., 2016).”
Invariant Risk Minimization (2019, background): “Second, we could minimize R(f) = maxe∈Etr R (f) − re, a robust learning objective where the constants re serve as environment baselines [2, 6, 15, 46].”
Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization (2019, background): “In the convex and batch case, there is a rich literature on distributionally robust optimization which treats the problem as a standard convex conic program (Ben-Tal et al., 2013; Duchi et al., 2016; Bertsimas et al., 2018; Lam & Zhou, 2015).”
Fairness risk measures (2019, background): “The idea of moving beyond expectations to a general aggregation of the per-instance losses has precedent in learning theory [Chapelle et al., 2001, Maurer and Pontil, 2009] and robust optimisation [Duchi et al., 2016, Gotoh et al., 2018].”
Robust Wasserstein profile inference and applications to machine learning (2016, methodology): “A profile function based approach towards calibrating the radius of uncertainty in the context of empirical likelihood based DRO can be found in [26, 14, 20, 25].”
Invariant Risk Minimization Games (2020, methodology): “When only training data sources are given, robust optimization techniques find the worst case loss over all possible convex combinations of the training sources (Mohri et al., 2019; Hoffman et al., 2018; Lee & Raginsky, 2018; Duchi et al., 2016).”
Adaptive Risk Minimization: A Meta-Learning Approach for Tackling Group Shift (2020, methodology): “DRO methods optimize machine learning systems to be robust to adversarial data distributions, thus optimizing for worst case performance against distribution shift [21, 5, 42, 16, 47, 15, 7].”
BREEDS: Benchmarks for Subpopulation Shift (2020, background): “Distribution shifts that are small with respect to some f -divergence have been studied in prior theoretical work [Ben+13; DGN16; EK18; ND16].”
Distributionally Robust Language Modeling (2019, background): “Optimizing on a ball of distributions around the empirical distribution has been considered in prior work (Ben-Tal et al., 2013; Namkoong and Duchi, 2017; Duchi and Namkoong, 2016; Sinha et al., 2018).”
Distributionally Robust Neural Networks (2020, background): “This is an instance of distributionally robust optimization (DRO), which studies worst-case performance over potential test distributions (Ben-Tal et al., 2013; Duchi et al., 2016).”
Environment Inference for Invariant Learning (2020, background): “Rather than optimizing a notion of invariance, Distributionally Robust Optimization (DRO) (Duchi et al., 2021) seeks good performance for all nearby distributions by minimizing the worst-case loss: max q E q [ (cid:96) ] s.t.”
Just Train Twice: Improving Group Robustness without Training Group Information (2021, methodology): “Many approaches for this setting fall under the DRO framework, where models are trained to minimize the worst-case loss across all distributions in a ball around the empirical distribution (Ben-Tal et al., 2013; Lam & Zhou, 2015; Duchi et al., 2016; Namkoong & Duchi, 2017; Oren et al., 2019).”
Towards Out-Of-Distribution Generalization: A Survey (2021, methodology): “For f -divergence-based DRO methods, Duchi et al. [133] show that the formulation (21) with distribution set P ( P tr ) = P ρ,n = { p ∈ R n : p T 1 = 1 , p ≥ 0 , D f ( p (cid:107) 1 /n ) ≤ ρ/n } is a convex approximation to regularizing the empirical risk by variance.”