Paper: arXiv 2504.07728

Authors: Anand Deo, Karthyek Murthy

Abstract

We study the problem of resource provisioning under stringent reliability or service level requirements, which arise in applications such as power distribution, emergency response, cloud server provisioning, and regulatory risk management. With chance-constrained optimization serving as a natural starting point for modeling this class of problems, our primary contribution is to characterize how the optimal costs and decisions scale for a generic joint chance-constrained model as the target probability of satisfying the service/reliability constraints approaches its maximal level. Beyond providing insights into the behavior of optimal solutions, our scaling framework has three key algorithmic implications. First, in distributionally robust optimization (DRO) modeling of chance constraints, we show that widely used approaches based on KL-divergences, Wasserstein distances, and moments heavily distort the scaling properties of optimal decisions, leading to exponentially higher costs. In contrast, incorporating marginal distributions or using appropriately chosen f-divergence balls preserves the correct scaling, ensuring decisions remain conservative by at most a constant or logarithmic factor. Second, we leverage the scaling framework to quantify the conservativeness of common inner approximations and propose a simple line search to refine their solutions, yielding near-optimal decisions. Finally, given N data samples, we demonstrate how the scaling framework enables the estimation of approximately Pareto-optimal decisions with constraint violation probabilities significantly smaller than the Omega(1/N)-barrier that arises in the absence of parametric assumptions

Complexity vs Empirical Score

  • Math Complexity: 8.5/10
  • Empirical Rigor: 3.0/10
  • Quadrant: Lab Rats — theoretically deep, empirically untested

Why this score: The paper presents a rigorous theoretical framework using large deviations and extreme value theory to characterize scaling in chance-constrained and distributionally robust optimization. While mathematically advanced and novel in its insights, it is purely theoretical and lacks empirical backtests or data-driven experiments in the provided text.

Research Flowchart

  flowchart TD
    A[Goal: Characterize optimal cost & decision scaling in chance-constrained optimization as reliability -> 1] --> B[Input: Joint Chance-Constrained Optimization Model & N Data Samples]
    B --> C[Develop Analytical Scaling Framework for High Reliability Limits]
    C --> D1[Evaluate DRO Models: KL, Wasserstein, Moments vs f-Divergence & Marginals]
    C --> D2[Refine Inner Approximations via Scaling-Based Line Search]
    C --> D3[Estimate Decisions Beyond the Ω 1/N Sample Limit]
    D1 & D2 & D3 --> E[Outcomes: Identified DRO scaling distortions, achieved near-optimal decisions, and enabled ultra-reliable data-driven bounds]

Cited References (314)

  1. Machine learning and portfolio optimization (2018)
  2. Ambiguous chance constrained problems and robust optimization (2005) — link
  3. State-dependent importance sampling for rare-event simulation: An overview and recent advances. (2012)
  4. Designing robust emergency medical service via stochastic programming (2004)
  5. Recent optimization models and trends in location, relocation, and dispatching of emergency medical vehicles (2019)
  6. Optimization problems with perturbations: A guided tour (1998)
  7. Directional derivatives of optimal solutions in smooth nonlinear programming (1992)
  8. The distributionally robust chance-constrained vehicle routing problem (2020)
and 306 more
  1. The robust capacitated vehicle routing problem under demand uncertainty (2013)
  2. On distributionally robust extreme value analysis (2020)
  3. Exact algorithms for the chance-constrained vehicle routing problem (2018)
  4. An integer programming approach for linear programs with probabilistic constraints (2010)
  5. Bicriteria Approximation of Chance-Constrained Covering Problems (2020) — link
  6. A probabilistic quality of service constraint for a location model of switches in ATM communications networks (2000)
  7. Topological optimization of reliable networks under dependent failures (2015)
  8. On distributionally robust chance constrained programs with Wasserstein distance (2021)
  9. On distributionally robust chance-constrained linear programs (2006)
  10. Achieving Efficiency in Black-Box Simulation of Distribution Tails with Self-Structuring Importance Samplers (2023)
  11. Perturbation analysis of optimization problems (2013)
  12. Combining Retrospective Approximation with Importance Sampling for Optimising Conditional Value at Risk (2022) — link
  13. Convergence of probability measures (2013)
  14. Introduction to rare event simulation (2013)
  15. On the Rate of Convergence of Optimal Solutions of Monte Carlo Approximations of Stochastic Programs (2000) — link
  16. Computational study of a chance constrained portfolio selection problem (2009)
  17. Semi-parametric estimation of the second order parameter in statistics of extremes (2002)
  18. Portfolio optimization under expected shortfall: contour maps of estimation error (2018)
  19. Risk-sensitive and robust decision-making: a cvar optimization approach (2015)
  20. Extreme value theory: an introduction (2007)
  21. Stochastic network design for disaster preparedness (2015)
  22. Two-Stage Robust Network Flow and Design Under Demand Uncertainty (2007) — link
  23. Ambulance Emergency Response Optimization in Developing Countries (2020)
  24. On regular variation of probability densities (1987)
  25. Portfolio value-at-risk with heavy-tailed risk factors (2002)
  26. Asymptotic representations for importance-sampling estimators of value-at-risk and conditional value-at-risk (2010)
  27. Simulating sensitivities of conditional value at risk (2009)
  28. Portfolio optimization with conditional value-at-risk objective and constraints (2002)
  29. Conditional value-at-risk in portfolio optimization: Coherent but fragile (2011)
  30. On optimal portfolio diversification with respect to extreme risks (2010)
  31. Quantitative risk management: concepts, techniques and tools-revised edition (2015)
  32. Heavy-tail phenomena: probabilistic and statistical modeling (2007)
  33. Extreme values, regular variation and point processes (2013)
  34. Optimization of conditional value-at-risk (2000)
  35. Kullback-Leibler divergence constrained distributionally robust optimization (2013)
  36. Risk-budgeting multi-portfolio optimization with portfolio and marginal risk constraints (2018)
  37. Solving chance-constrained optimization problems with stochastic quadratic inequalities (2016)
  38. Distributionally robust linear and discrete optimization with marginals (2022)
  39. Sample average approximation method for chance constrained programming: theory and applications (2009)
  40. Multivariate peaks over thresholds models (2018)
  41. Extreme-value copulas (2010)
  42. Distributionally robust joint chance constraints with second-order moment information (2011) — link
  43. Optimization of convex risk functions (2006)
  44. Optimizing the CVaR via sampling (2014) — link
  45. Optimizing tail risks using an importance sampling based extrapolation for heavy-tailed objectives (2020)
  46. Lectures on stochastic programming: modeling and theory (2021)
  47. Modelling extremal events: for insurance and finance (2013)
  48. Large deviations in multifactor portfolio credit risk (2007)
  49. Sparse structures for multivariate extremes (2021)
  50. Multivariate regular variation on cones: application to extreme values, hidden regular variation and conditioned limit laws (2008)
  51. Graphical models for extremes (2020)
  52. Importance sampling for portfolio credit risk (2005)
  53. A Unified Approach to Risk Management (2010)
  54. How likely is contagion in financial networks? (2015)
  55. Monte Carlo Methods in Financial Engineering (2013)
  56. Stochastic simulation: algorithms and analysis (2007)
  57. Max-stable models for multivariate extremes (2012) — link
  58. Continuous multivariate distributions, Volume 1: Models and applications (2004)
  59. Credit risk modeling: theory and applications (2009)
  60. Envelope theorems for arbitrary choice sets (2002)
  61. Chance-constrained programming (1959)
  62. Data-Driven Patient Scheduling in Emergency Departments: A Hybrid Robust-Stochastic Approach (2019) — link
  63. Deterministic Equivalents for Optimizing and Satisficing under Chance Constraints (1963) — link
  64. Chance constrained programming with joint constraints (1965)
  65. On probabilistic constrained programming (1970)
  66. Slow adaptive OFDMA systems through chance constrained programming (2010)
  67. Robust chance-constrained optimization for power-efficient and secure SWIPT systems (2017)
  68. An exact solution approach for portfolio optimization problems under stochastic and integer constraints (2009)
  69. Stochastic optimization of insurance portfolios for managing exposure to catastrophic risks (2000)
  70. DC optimal power flow with joint chance constraints (2020)
  71. Random fields and geometry (2007)
  72. How to make a Hill plot (2000)
  73. Smoothing the Hill estimator (1997)
  74. Data-driven chance constrained programs over Wasserstein balls (2024)
  75. Time series analysis (1994) — link
  76. The t copula and related copulas (2005)
  77. On the pricing of corporate debt: The risk structure of interest rates (1974)
  78. Chance-constrained problems and rare events: an importance sampling approach (2016)
  79. Optimization under rare chance constraints (2022)
  80. Solving chance-constrained stochastic programs via sampling and integer programming (2008)
  81. Some remarks on the value-at-risk and the conditional value-at-risk (2000)
  82. Approximation and estimation of very small probabilities of multivariate extreme events (2016)
  83. Approximation of high quantiles from intermediate quantiles (2016)
  84. A high quantile estimator based on the log-generalized Weibull tail limit (2018)
  85. Data-driven chance constrained stochastic program (2016)
  86. A sample approximation approach for optimization with probabilistic constraints (2008)
  87. The scenario approach to robust control design (2006)
  88. Topics in optimal transportation (2003)
  89. Contagion in Financial Networks. (2010)
  90. Systemic Risk in Banking Ecosystems (2011)
  91. Failure and Rescue in an Inter-Bank Network (2013)
  92. Financial Contagion (2000)
  93. On exact sampling of stochastic perpetuities. (2011)
  94. Limiting forms of the frequency distribution of the largest or smallest member of a sample (1928)
  95. Sur la distribution limite du terme maximum d’une serie aleatoire (1943)
  96. Statistics of extremes (2012)
  97. Financial ratios and the probabilistic prediction of bankruptcy (1980)
  98. Bankruptcy prediction with industry effects (2004)
  99. Affine models for credit risk analysis (2006)
  100. Methodological issues related to the estimation of financial distress prediction models (1984)
  101. In search of distress risk (2008)
  102. Multiperiod corporate default prediction with the partially-conditioned forward intensity (2013)
  103. Frailty correlated default (2009)
  104. Deep learning for mortgage risk (2016) — link
  105. Towards explainable ai: Significance tests for neural networks (2019) — link
  106. Common failings: How corporate defaults are correlated (2007)
  107. Portfolio credit risk with extremal dependence: Asymptotic analysis and efficient simulation (2008)
  108. Default clustering in large pools: Large deviations (2015)
  109. Risk analysis for large pools of loans (2019)
  110. Covariance regularization by thresholding (2008)
  111. Consistency and asymptotic normality of the maximum likelihood estimator in generalized linear models (1985)
  112. Martingale limit theory and its application (2014)
  113. Asymptotic statistics (2000)
  114. Introduction to time series and forecasting (2002)
  115. Uniform convergence in probability and stochastic equicontinuity (1991)
  116. Weak convergence (1996)
  117. An introduction to probability theory and its applications, vol 2 (2008)
  118. Sensitivity based neural networks explanations (2018) — link
  119. An introduction to statistical learning (2013)
  120. Handbook of Heavy Tailed Distributions in Finance: Handbooks in Finance, Book 1 (2003)
  121. Fat-tailed and skewed asset return distributions: implications for risk management, portfolio selection, and option pricing (2005)
  122. Limit theory for multivariate sample extremes (1977)
  123. Estimation of extreme risk regions under multivariate regular variation (2011)
  124. Estimation of the marginal expected shortfall: the mean when a related variable is extreme (2015)
  125. Chance-constrained optimal power flow: Risk-aware network control under uncertainty (2014)
  126. Chance-Constrained Day-Ahead Scheduling in Stochastic Power System Operation (2014) — link
  127. Stochastic optimal power flow based on conditional value at risk and distributional robustness (2015)
  128. Data-driven distributionally robust optimal power flow for distribution systems (2018)
  129. Generalized PageRank on directed configuration networks (2017)
  130. Convergence of the Population Dynamics algorithm in the Wasserstein metric (2019)
  131. PageRank in undirected random graphs (2015)
  132. PageRank on inhomogeneous random digraphs (2020)
  133. Local weak convergence for PageRank (2020)
  134. A Dynamic Network Model of Interbank Lending—Systemic Risk and Liquidity Provisioning (2020)
  135. Mean field games and systemic risk (2013)
  136. Domains of attraction and regular variation in IRd (1984)
  137. Improved algorithms for rare event simulation with heavy tails (2006)
  138. Heavy tails, importance sampling and cross–entropy (2005)
  139. Variational analysis (2009)
  140. Convergence of dynamic programming models (1981)
  141. On law invariant coherent risk measures (2001)
  142. A theory for measures of tail risk (2021)
  143. Computing VaR and CVaR using stochastic approximation and adaptive unconstrained importance sampling (2009)
  144. The big data newsvendor: Practical insights from machine learning (2019)
  145. Deep learning (2016)
  146. High-dimensional semiparametric Gaussian copula graphical models (2012)
  147. An introduction to copulas (2007)
  148. Dependence modeling with copulas (2014)
  149. Affine point processes: Approximation and efficient simulation (2015)
  150. Optimal scenario generation for heavy-tailed chance constrained optimization (2020) — link
  151. On mixing sets arising in chance-constrained programming (2012)
  152. Probabilistically constrained linear programs and risk-adjusted controller design (2005)
  153. On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty (2002)
  154. Efficient rare-event simulation for the maximum of heavy-tailed random walks (2008)
  155. Distributionally robust chance-constrained programs with right-hand side uncertainty under Wasserstein ambiguity (2022)
  156. On safe tractable approximations of chance constraints (2012)
  157. Asymptotics and fast simulation for tail probabilities of maximum of sums of few random variables (2007)
  158. Rare-event simulation techniques: an introduction and recent advances (2006)
  159. Dependence structures for multivariate high-frequency data in finance (2003)
  160. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead (2019)
  161. Quantile tomography: using quantiles with multivariate data (2012)
  162. Poisson approximation (2019)
  163. Dynamic clearing and contagion in financial networks (2018) — link
  164. Contagion! Systemic risk in financial networks (2016)
  165. Contagion in financial networks (2016)
  166. Large deviations techniques and applications (2009)
  167. Sequential convex approximations to joint chance constrained programs: A Monte Carlo approach (2011)
  168. Mathematics for economists (1994)
  169. Solving chance-constrained problems via a smooth sample-based nonlinear approximation (2020)
  170. Correlation and dependence in risk management: properties and pitfalls (2002)
  171. Multivariate Archimedean copulas, d-monotone functions and l 1-norm symmetric distributions (2009)
  172. Systemic risk in financial systems (2001)
  173. Impact of intentional islanding of distributed generation on electricity market prices (2006)
  174. Beyond correlation: Extreme co-movements between financial assets (2002)
  175. Eventual convexity of probability constraints with elliptical distributions (2019)
  176. Efficient Scenario Generation for Heavy-Tailed Chance Constrained Optimization (2023)
  177. Eventual convexity of chance constrained feasible sets (2015)
  178. Convexity and optimization with copul \ae structured probabilistic constraints (2016)
  179. The objective method: probabilistic combinatorial optimization and local weak convergence (2004)
  180. Random graphs and complex networks (2009)
  181. Robust empirical optimization is almost the same as mean–variance optimization (2018)
  182. Financial prediction with constrained tail risk (2007)
  183. On the coherence of expected shortfall (2002)
  184. Asymptotic analysis of stochastic programs (1991)
  185. Convex approximations of chance constrained programs (2007)
  186. From CVaR to uncertainty set: Implications in joint chance-constrained optimization (2010)
  187. Conditional value-at-risk for general loss distributions (2002)
  188. Spectral measures of risk: A coherent representation of subjective risk aversion (2002)
  189. Value-at-risk vs. conditional value-at-risk in risk management and optimization (2008)
  190. Expected shortfall: a natural coherent alternative to value at risk (2002)
  191. Coherent measures of risk (1999)
  192. Coherent approaches to risk in optimization under uncertainty (2007)
  193. Statistical inference using extreme order statistics (1975)
  194. Refined Pickands estimators of the extreme value index (1995)
  195. Generalized Pickands estimators for the extreme value index (2005)
  196. Portfolio optimization for heavy-tailed assets: Extreme Risk Index vs. Markowitz (2015)
  197. Risk in a large claims insurance market with bipartite graph structure (2016)
  198. Diffusions, Markov processes and martingales: Volume 2, It ^o calculus (2000)
  199. Numerical solution of stochastic differential equations (2013)
  200. Forecasting bankruptcy more accurately: A simple hazard model (2001)
  201. Spectra of some self-exciting and mutually exciting point processes (1971)
  202. Modeling financial contagion using mutually exciting jump processes (2015)
  203. Approximation capabilities of multilayer feedforward networks (1991)
  204. Transform analysis and asset pricing for affine jump-diffusions (2000)
  205. Autoregressive conditional heteroscedasticity with estimates of the variance of United Kingdom inflation (1982)
  206. Hawkes processes (2015) — link
  207. Advanced econometrics (1985)
  208. Correlation in corporate defaults: Contagion or conditional independence? (2010)
  209. Explaining explanations: An overview of interpretability of machine learning (2018)
  210. Sensitivity analysis of the Eisenberg–Noe model of contagion (2010)
  211. Uniqueness of equilibrium in a payment system with liquidation costs (2016)
  212. Optimization of fire sales and borrowing in systemic risk (2019)
  213. Systemic risk with central counterparty clearing (2014)
  214. Inhomogeneous financial networks and contagious links (2016)
  215. Stress testing the resilience of financial networks (2012)
  216. The PageRank citation ranking: Bringing order to the web. (1999)
  217. Stochastic recursions on directed random graphs (2020) — link
  218. Mass Transportation Problems: Applications (2006)
  219. Mass Transportation Problems: Volume 1: Theory (2006)
  220. Robust risk management via multi-marginal optimal transport (2024)
  221. A limit theorem for “Quicksort” (1991)
  222. A fixed point theorem for distributions (1992)
  223. Convergence of a branching type recursion (1996)
  224. Analysis of recursive algorithms by the contraction method (1996)
  225. Optimal transport: old and new (2008)
  226. Probability, volume 95 of (1996)
  227. Efficient simulation for expectations over the union of half-spaces (2018)
  228. Convergence of dynamic programming models (1981)
  229. Deep learning (2016)
  230. Tail index estimation for dependent data (1998)
  231. Using a bootstrap method to choose the sample fraction in tail index estimation (2001)
  232. A multivariate exponential distribution (1967)
  233. Managing default contagion in inhomogeneous financial networks (2019)
  234. Bootstrap percolation in directed and inhomogeneous random graphs (2015) — link
  235. Hidden regular variation, second order regular variation and asymptotic independence (2002)
  236. Rare-Event simulation for neural network and random forest predictors (2020) — link
  237. Multilevel splitting for estimating rare event probabilities (1999)
  238. Newsvendor solutions via conditional value-at-risk minimization (2007)
  239. Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations (2018)
  240. Double/debiased machine learning for treatment and structural parameters (2018)
  241. Orthogonal statistical learning (2019) — link
  242. Locally robust semiparametric estimation (2022)
  243. The influence function of semiparametric estimators (2022)
  244. The asymptotic variance of semiparametric estimators (1994)
  245. Demystifying statistical learning based on efficient influence functions (2022)
  246. Debiasing in-sample policy performance for small-data, large-scale optimization (2022)
  247. Distributionally robust optimization under moment uncertainty with application to data-driven problems (2010)
  248. Robust sample average approximation (2018)
  249. Data-driven robust mean-CVaR portfolio selection under distribution ambiguity (2019)
  250. A risk-averse newsvendor model under the CVaR criterion (2009)
  251. Adaptive Importance Sampling for Efficient Stochastic Root Finding and Quantile Estimation (2021) — link
  252. Dominating points of Gaussian extremes (2018) — link
  253. The cross-entropy method for continuous multi-extremal optimization (2006)
  254. The cross-entropy method for combinatorial and continuous optimization (1999)
  255. On multivariate Gaussian tails (2003)
  256. Deep Probabilistic Accelerated Evaluation: A Certifiable Rare-Event Simulation Methodology for Black-Box Autonomy (2020) — link
  257. Importance sampling in the Monte Carlo study of sequential tests (1976)
  258. Fast simulation of rare events in queueing and reliability models (1995)
  259. Rare Event Simulation for Queues. (2009)
  260. State-dependent importance sampling for rare-event simulation: An overview and recent advances (2012)
  261. Fast simulation of multifactor portfolio credit risk (2008)
  262. Simulating risk contributions of credit portfolios (2015)
  263. Rare events simulation for heavy-tailed distributions (2000)
  264. Simulating heavy tailed processes using delayed hazard rate twisting (2002)
  265. Importance sampling for sums of random variables with regularly varying tails (2007)
  266. Efficient splitting-based rare event simulation algorithms for heavy-tailed sums (2013)
  267. Efficient simulation of tail probabilities of sums of correlated lognormals (2011)
  268. Activity networks: Project planning and control by network models (1977)
  269. Markov and Markov-regenerative PERT networks (1986)
  270. The variation of certain speculative prices (1997)
  271. Variational analysis (2009)
  272. Rare-event simulation for distribution networks (2019)
  273. On Kusuoka representation of law invariant risk measures (2013)
  274. Generalized elliptical distributions: theory and applications (2004)
  275. Achieving Efficiency in Black Box Simulation of Distribution Tails with Self-structuring Importance Samplers (2021) — link
  276. Distributionally robust tail bounds based on Wasserstein distance and $ f $-divergence (2021) — link
  277. An Application of Chance Constrained Programming to Portfolio Selection in a Casualty Insurance Firm (1969) — link
  278. Expectation and Chance-Constrained Models and Algorithms for Insuring Critical Paths (2010) — link
  279. QoS-Aware Data Center Operations Based on Chance- and Risk-Constrained Optimization (2022) — link
  280. Overcommitment in Cloud Services: Bin Packing with Chance Constraints (2019) — link
  281. Ambulance location under stochastic demand: A sampling approach (2016) — link
  282. The Maximum Availability Location Problem (1989) — link
  283. Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach (2003) — link
  284. Incorporating Asymmetric Distributional Information in Robust Value-at-Risk Optimization (2008) — link
  285. Decomposition algorithms for optimizing multi-server appointment scheduling with chance constraints (2016)
  286. Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning (2021) — link
  287. Slow Adaptive OFDMA Systems Through Chance Constrained Programming (2010) — link
  288. Distributionally Robust Chance Constrained Optimal Power Flow with Renewables: A Conic Reformulation (2018) — link
  289. Staffing Call Centers with Uncertain Demand Forecasts: A Chance-Constrained Optimization Approach (2010) — link
  290. The beta-Reliable Median on a Network with Discrete Probabilistic Demand Weights (2007) — link
  291. Multisourcing Supply Network Design: Two-Stage Chance-Constrained Model, Tractable Approximations, and Computational Results (2017) — link
  292. A chance-constrained two-stage stochastic programming model for humanitarian relief network design (2018) — link
  293. Programming under probabilistic constraint with discrete random variable (1998)
  294. Concavity and efficient points of discrete distributions in probabilistic programming (2000)
  295. Price of Correlations in Stochastic Optimization (2012) — link
  296. Chance-constrained optimization under limited distributional information: A review of reformulations based on sampling and distributional robustness (2022) — link
  297. Ambiguous Joint Chance Constraints Under Mean and Dispersion Information (2017) — link
  298. Optimization under rare events: scaling laws for linear chance-constrained programs (2024) — link
  299. Optimization of conditional value-at-risk (2000)
  300. Optimization with Marginals and Moments (2021)
  301. From Data to Decisions: Distributionally Robust Optimization Is Optimal (2021) — link
  302. A Pareto Dominance Principle for Data-Driven Optimization (2024) — link
  303. Temperature Overloads in Power Grids Under Uncertainty: A Large Deviations Approach (2019) — link
  304. Joint Mixability (2016) — link
  305. Distributionally Robust Optimization with Markovian Data (2021) — link
  306. Distributionally robust chance constraints for non-linear uncertainties (2016)

0 of 314 cited works are in the corpus; resolved via arXiv source bundles, Semantic Scholar and OpenAlex. Corpus-wide: 2518 linked papers.